POJ 3255 Roadblocks

PS: 次短路问题。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <vector>
#include <cmath>
const int INF = 0x3ffffff;
using namespace std;
const int MAXN = 5100;
struct edge {
    int to, cost;
};
typedef pair<int, int> P;
int dist[MAXN];
int dist2[MAXN];
vector<edge> G[MAXN];
//Accepted	3676K	188MS	G++	1575B	2014-06-04 20:16:12
int N, R;
priority_queue<P, vector<P>, greater<P> > que;
void solve() {
    while(!que.empty()) que.pop();
    fill(dist, dist+N, INF);
    fill(dist2, dist2+N, INF);
    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 < (int)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));
            }
        }
    }
    printf("%d\n", dist2[N-1]);
}

int main() {
    edge in;
    int x, y, w;
    while(scanf("%d%d", &N, &R) != EOF) {
        for(int i = 0; i < N; i++) G[i].clear();
        for(int i = 1; i <= R; i++) {
            scanf("%d%d%d", &x, &y, &w);
            x--; y--;
            in.to = y;
            in.cost = w;
            G[x].push_back(in);
            in.to = x;
            G[y].push_back(in);
        }
        solve();
    }
    return 0;
}

POJ 3255 Roadblocks,古老的榕树,5-wow.com