POJ.3255 Roadblocks

1.Problem
http://poj.org/problem?id=3255

2.Idea
Using 2 arrays for the shortest and the second shortest paths while updating by Dijkstra.

3.Source

 #define MAX_N 5000  
 struct edge { int to, cost; };  
 int N, R;  
 vector<edge> G[MAX_N];  
 int dist[MAX_N];  
 int dist2[MAX_N];  
 void solve()  
 {  
      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;  
 }  
 int main()  
 {  
      cin >> N >> R;  
      for (int i = 0; i < R; i++) {  
           int a, b, d;  
           cin >> a >> b >> d;  
           a--;  
           b--;  
           edge e1; e1.to = b; e1.cost = d;  
           edge e2; e2.to = a; e2.cost = d;  
           G[a].push_back(e1);  
           G[b].push_back(e2);  
      }  
      solve();  
      return 0;  
 }