p2865 路障 次短路长度（dijkstra+优先队列）

· · 题解

updata：被Dalao叉了嘤嘤嘤QAQ...... 正如Dalao所说，嘤该在修改最短路的时候把最短路的长度赋值给次短路QAQ 加了一句话QAQ (Ps:现在看自己码风好怪QAQ凑合着看吧QAQ)

次短路应该会和最短路有关系，想到dijkstra，SPFA...(关于SPFA......)对于新加入的一条边，无非几种情况：

(1).更新了最短路

(2).无法更新最短路，有可能更新次短路

(3).无法更新次短路和最短路

注意的地方：

更新最短路后要把原最短路赋值给最短路(免得被叉QAQ)

情况2只有满足加入当前边后严格长于最短，才去更新次短路

次短路当然更新不了最短路啦Baka！QAQ

如果求稳还是dij吧QAQ

#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 101000
#include<queue>
using namespace std;
int tot=0,head[4*maxn],dist1[maxn],dist2[maxn];
int m,ed;
struct node
{
    int v,val,next;
}edge[200000];
void add(int x,int y,int val)
{
     tot++;
     edge[tot].v=y;
     edge[tot].val=val;
     edge[tot].next=head[x];
     head[x]=tot;
     tot++;
     edge[tot].v=x;
     edge[tot].val=val;
     edge[tot].next=head[y];
     head[y]=tot;
}
void dijkstra()
{
    //memset(vis,0,sizeof(vis));
    memset(dist1,0x3F,sizeof(dist1));
    memset(dist2,0x3F,sizeof(dist2)); 
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push(make_pair(0,1));
    dist1[1]=0;
    while(!q.empty())
    {
        int temp=q.top().second,dis=q.top().first;
        q.pop(); 
        if(dis>dist2[temp]) continue;
        for(int i=head[temp];i;i=edge[i].next)
        {
            int cnt=edge[i].v;
             if(dist1[cnt]>dis+edge[i].val)
            {   
                dist2[cnt]=dist1[cnt];
                dist1[cnt]=dis+edge[i].val;
                q.push(make_pair(dist1[cnt],cnt));
            } 
             if(dist2[cnt]>dis+edge[i].val&&dis+edge[i].val>dist1[cnt])/**/
             {
                dist2[cnt]=dis+edge[i].val; 
                q.push(make_pair(dist2[cnt],cnt));
             }    
        }
    }

}
int main()
{
    cin>>ed>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,val;
        cin>>x>>y>>val;
        add(x,y,val);
    }
    dijkstra();
    cout<<dist2[ed]<<endl;
    return 0;
 }