POJ 3255 Roadblocks（次短路模板题）

题目链接

#include<bits/stdc++.h>

using namespace std;

#define maxn 5005
#define ll long long
typedef pair<int,int>PII;
const int INF = 1e9+7;

int n,r;
int dis[maxn],dis2[maxn];
struct edge{
    int to,cost;
    edge(int x,int y){
        to=x;
        cost=y;
    }
};
vector<edge>G[maxn];

void dijkstra(int s) {
    priority_queue<PII,vector<PII>,greater<PII> >que;
    for(int i=0;i<=n;i++)dis[i]=INF;
    for(int i=0;i<=n;i++)dis2[i]=INF;
    dis[s]=0;
    que.push(PII(0,s));
    while(!que.empty()){
        PII p=que.top();que.pop();
        int v=p.second,d=p.first;
        if(dis2[v]<d)continue;
        for(int i=0;i<G[v].size();i++) {
            edge e=G[v][i];
            int d2=d+e.cost;
            if(dis[e.to]>d2){
                swap(dis[e.to],d2);
                que.push(PII(dis[e.to],e.to));
            }
            if(dis2[e.to]>d2&&dis[e.to]<d2){
                dis2[e.to]=d2;
                que.push(PII(dis2[e.to],e.to));
            }
        }
    }
}
int main()
{
    scanf("%d %d",&n,&r);
    for(int i=0;i<r;++i){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        G[a].push_back(edge(b,c));
        G[b].push_back(edge(a,c));
    }
    dijkstra(1);
    printf("%d",dis2[n]);
    return 0;
}