POJ 3255 Roadblocks （Dijkstra求最短路径的变形）（Dijkstra求次短路径）

Roadblocks

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 16425		Accepted: 5797

Description

Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.

The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.

The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).

Input

Line 1: Two space-separated integers: N and R
Lines 2..R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)

Output

Line 1: The length of the second shortest path between node 1 and node N

Sample Input

Sample Output

Hint

Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)

这题用Dijkstra算法求就可以了，我们维护两个数组，d1[],d2[]。

d1保存最短路径，d2保存次短路径

我们考虑到，分两种情况：

1.当我们队列中的点没有更新相邻点的最短路径，我们就用它更新次短路径。

2.如果我们队列中的点更新了相邻点的最短路径，我们就用原先的最短路径更新次短路径。

总而言之：

　　就是用所有非形成最短路径的边更新次短路径。

Dijkstra算法求单元最短路径：http://www.cnblogs.com/zhangjiuding/p/7712592.html

代码：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <queue> 
using namespace std;
typedef long long ll;
#define MAX_N 5010
#define INF 2147483647

typedef pair<int,int> P; //first是最短距离，second是顶点编号 

struct edge{
    int to,cost;
};

int n,r;   //顶点数，边数 
vector <edge> G[MAX_N]; //图的邻接表表示，G[x]表示点x相连的所有的边的集合 

int dist1[MAX_N];   //最短路径 
int dist2[MAX_N];   //次短路径 

void solve(){
    //通过指定greater<P>参数，堆按照first从小到大的顺序取出值。 
    priority_queue<P, vector<P>, greater<P> > que;
    fill(dist1, dist1+n, INF);
    fill(dist2, dist2+n, INF);
    dist1[0] = 0;
    que.push(P(0,0));
    
    
    while(!que.empty()){
        P p = que.top(); que.pop();
        int v = p.second, d = p.first;//取出编号和距离 
        
        //如果次短距离比之前加入这个点短，说明加入这个点之后又更新过
        //这里continue相当于一种剪枝，没有这句也不会错，但是加了效率会变高 
        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(dist1[e.to] > d2){
                swap(dist1[e.to] ,d2); //把之前的距离取出来，更新次短路径 
                que.push(P(dist1[e.to], e.to)) ;  // 把更新过的点加入队列，用这个点去更新其他点 
            }
            //如果d2没有更新过这个点的最短路径，就直接用d2更新次短路径
            //如果d2更新过这个点的最短路径，就用d2交换出来的值更新次短路径 
            if(dist2[e.to] > d2 && dist1[e.to] < d2){
                dist2[e.to] = d2;
                que.push(P(dist2[e.to], e.to));
            }
        }
    }
    printf("%d
",dist2[n-1]);
} 

int main(){
    cin >> n >> r;
    int x,y,d;
    for(int i = 0;i < r; i++){
        edge e;
        cin >> x >> y >> d;
        e.cost = d;e.to = y-1;
        G[x-1].push_back(e);
        e.to = x-1;
        G[y-1].push_back(e);
    } 
    solve();
    return 0;
}