poj Roadblocks 次短路（數據較大）

[cpp]
/*這種思路是在網上借鑒的。很好。速度也非常快。自己實現了一遍。在poj上181MS。
主要是分別一起點和終點為源點作兩次spfa。
然後次短路必定是dist[u]+w+rdist[v]。
枚舉邊。u,v,為邊的兩個端點，w為邊的權值。
這個值需要滿足的條件是  >dist[n]，然後再最小值。*/ 
#include <stdio.h> 
#include <cstring> 
#include <iostream> 
#include <queue> 
using namespace std; 
const int maxn=5001; 
const int maxm=100001; 
const int inf=99999999; 
struct edge 
{ 
    int from,to,next,w; 
}e[maxm<<1]; 
int head[maxn]; 
bool vis[maxn]; 
int dis[maxn]; 
int rdis[maxn]; 
int n,m,t; 
void add(int i,int j,int w) 
{ 
    e[t].from=i; 
    e[t].to=j; 
    e[t].w=w; 
    e[t].next=head[i]; 
    head[i]=t++; 
} 
void spfa(int s,int d[]) 
{ 
    queue <int> q; 
    q.push(s); 
    memset(vis,false,sizeof(vis)); 
    d[s]=0; 
    vis[s]=true; 
    while(!q.empty()) 
    { 
        int u=q.front(); 
        q.pop(); 
        vis[u]=false; 
        for(int i=head[u];i!=-1;i=e[i].next) 
        { 
            int v=e[i].to; 
            if(d[v]>e[i].w+d[u]) 
            { 
                d[v]=e[i].w+d[u]; 
                if(!vis[v]) 
                { 
                    q.push(v); 
                    vis[v]=true; 
                } 
            } 
        } 
    } 
} 
int main() 
{ 
    scanf("%d%d",&n,&m); 
    int u,v,w; 
    t=1; 
    memset(head,-1,sizeof(head)); 
    for(int i=1;i<=m;i++) 
    { 
        scanf("%d%d%d",&u,&v,&w); 
        add(u,v,w); 
        add(v,u,w); 
    } 
    for(int i=1;i<=n;i++) 
    dis[i]=rdis[i]=inf; 
    spfa(1,dis); 
    spfa(n,rdis); 
    int min=inf; 
    for(int i=0;i<=t;i++) 
    { 
        int ans=e[i].w+dis[e[i].from]+rdis[e[i].to]; 
        if(ans>dis[n]&&ans<min) 
        min=ans; 
    } 
    printf("%d\n",min); 
    return 0; 
}