POJ - 3255 Roadblocks（Bellman-Ford的隊列優化---SPFA算法）

題目連結:https://cn.vjudge.net/contest/314508#problem/A

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

4 4
1 2 100
2 4 200
2 3 250
3 4 100
           

Sample Output

Hint

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

翻譯:

鄉村由R（1≤R≤100000）雙向道路組成，每個道路連接配接N（1≤N≤5000）個交叉口中的兩個，友善編号1…N。Bessie從交叉口1開始，她的朋友（目的地）在交叉口N，從1到N求一條次短路。

第二條最短路徑可以與任何最短路徑共享道路，也可以後退，即使用同一條道路或交叉口多次。第二最短路徑是長度長于最短路徑的最短路徑（即，如果存在兩條或更多最短路徑，則第二最短路徑是長度長于最短路徑但不長于任何其他路徑的路徑）。

分析:點的個數最大是5000，邊的個數是100000。可想而知，圖是非常大的。求最短的最優的算法當屬SPFA。邊的個數小于N*N，考慮用鄰接表存圖，雙向道路，要存兩次.

void serve(int a,int b,int c){
    u[k]=a,v[k]=b,w[k]=c;/*雙向道路鄰接表存法*/
    next[k]=first[a];
    first[a]=k;
    k++;
}
           

注：數組開的要比邊的二倍還要大。

求次短路，從1号頂點求一遍最短路，從N号頂點求一遍最短路。

次短路的可以表示為 d i s 1 [ u [ i ] ] + d i s 2 [ v [ i ] ] + w [ i ] dis1[u[i]]+dis2[v[i]]+w[i] dis1[u[i]]+dis2[v[i]]+w[i],但要保證此路程大于最短路。

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int v[200100],w[200100],u[200100];
int dis1[200100],dis2[200100];
int book[200100];
int first[200100],next[200100];
int n,m,k;
void serve(int a,int b,int c){
    u[k]=a,v[k]=b,w[k]=c;/*雙向道路鄰接表存法*/
    next[k]=first[a];
    first[a]=k;
    k++;
}
void SPFA(int x,int *dis){
    memset(book,0,sizeof(book));
    queue<int>Q1;
    Q1.push(x);
    dis[x]=0;
    book[x]=1;
    while(!Q1.empty()){
        int u=Q1.front();
        Q1.pop();
        book[u]=0;/*出隊操作*/
        for(int j=first[u]; j!=-1; j=next[j])//能否通過這條邊進行松弛操作
            if(dis[v[j]]>dis[u]+w[j]){
                dis[v[j]]=dis[u]+w[j];//先更新，再判斷是否入隊列
                if(book[v[j]]==0){/*判斷是否在隊列中*/
                    book[v[j]]=1;
                    Q1.push(v[j]);
                }
            }
    }
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        k=0;
        memset(first,-1,sizeof(first));
        memset(dis1,INF,sizeof(dis1));
        memset(dis2,INF,sizeof(dis2));
        for(int i=0; i<m; i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            serve(a,b,c);
            serve(b,a,c);
        }
        SPFA(1,dis1);
        SPFA(n,dis2);
        int mi=INF;
        for(int i=1; i<=n; i++){
            for(int j=first[i]; j!=-1; j=next[j]){
                int sum=dis1[i]+dis2[v[j]]+w[j];
                if(sum>dis1[n]&&sum<mi)
                    mi=sum;
            }
        }
        printf("%d\n",mi);

    }
    return 0;
}