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

补充：软件开发 , C++ ,