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;
}