(2番目の最短経路)POJ-3255-Roadblocks

問題URL→http://poj.org/problem?id=3255

蟻本に載っている問題。
2番目の最短路を求めるにはdistを2つ用意する。

/*
#include <bits/stdc++.h>
//*/
//*
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
//*/
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

#define int long long
#ifdef int
    const long long INF = LLONG_MAX / 10;
#else
    const int INF = 1010101010;
#endif

using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

struct edge
{
    int to;
    int cost;
    
    edge() {}
    edge(int to, int cost) : to(to), cost(cost) {}
};

int N, R;
vector<edge> G[5050];

int dist[5050];     //最短距離
int dist2[5050];    //2番目の最短距離

signed main()
{
    cin >> N >> R;
    REP(i,R) {
        int A, B, D;
        cin >> A >> B >> D;
        A--; B--;
        G[A].push_back(edge(B, D));
        G[B].push_back(edge(A, D));
    }

    //firstが小さい順に取り出せる
    //first:距離 second:頂点番号
    priority_queue<P, vector<P>, greater<P>> que;
    fill(dist, dist + N, INF);
    fill(dist2, dist2 + N, INF);
    dist[0] = 0;
    que.push(P(0, 0));

    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second, d = p.first;
        if (dist2[v] < d) continue;
        for (int i=0; i<G[v].size(); i++) {
            edge e = G[v][i];
            int d2 = d + e.cost;
            if (dist[e.to] > d2) {
                swap(dist[e.to], d2);
                que.push(P(dist[e.to], e.to));
            }
            if (dist2[e.to] > d2 && dist[e.to] < d2) {
                dist2[e.to] = d2;
                que.push(P(dist2[e.to], e.to));
            }
        }
    }

    cout << dist2[N - 1] << endl;
}