Help the Hurricane Victims 刪邊法的次短路

[cpp] 
/*之前用兩種方法寫過次短。分別是兩次的spfa和二維的dij。其中應該是以兩次的spfa的效率最高。二維dij可以很方便的統計次短路的數量。
而這二者對於次短路不存在的請在好像都難以判斷，反正我試過都沒有寫出來。
為了解決次短路不存在的狀況，使用刪邊法。
具體的操作就是先保存最短過程中的路徑，然後沿著路徑枚舉邊進行刪除，就是講邊的權值置為inf。
然後取最小即可。*/ 
#include <stdio.h> 
const int maxn=101; 
const int inf=1<<30; 
int map[maxn][maxn],n,m; 
int path[maxn],vis[maxn],dist[maxn],pre[maxn]; 
int dij() 
{ 
    for(int i=1;i<=n;i++) 
    pre[i]=1,vis[i]=false,dist[i]=inf; 
    dist[1]=path[1]=0; 
    for(int i=1;i<=n;i++) 
    { 
        int min=inf; 
        int k; 
        for(int j=1;j<=n;j++) 
        { 
            if(!vis[j]&&dist[j]<min) 
            min=dist[j],k=j; 
        } 
        if(k==n) break; 
        if(min==inf) break; 
        vis[k]=true; 
        for(int j=1;j<=n;j++) 
        { 
            if(dist[j]>dist[k]+map[k][j]&&!vis[j]) 
            dist[j]=dist[k]+map[k][j],pre[j]=k; 
        } 
    } 
    return dist[n]; 
} 
int cmin() 
{ 
    int ans=inf,t; 
    for(int i=1;i<=n;i++) 
    path[i]=pre[i];//必須用一個path來保存刪邊操作時的原圖的最短路徑，否則在做dij的過程中pre會改變 
    for(int i=n;i!=1;i=path[i]) 
    { 
        int temp=map[i][path[i]]; 
        map[i][path[i]]=map[path[i]][i]=inf; 
        t=dij(); 
        if(t<ans) ans=t; 
        map[i][path[i]]=map[path[i]][i]=temp; 
    } 
    return ans; 
} 
int main() 
{ 
    int u,v,w; 
    while(scanf("%d%d",&n,&m)==2) 
    { 
        if(n==0&&m==0) break; 
        for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++) 
        map[i][j]=inf; 
        while(m--) 
        {  www.2cto.com
            scanf("%d%d%d",&u,&v,&w); 
            map[u][v]=map[v][u]=w; 
        } 
        int ans1=dij();//dij必須先調用，否則值會發生改變 
        int ans=cmin(); 
        if(ans==inf) printf("Sorry, no different ways available.\n"); 
        else printf("%d %d\n",ans1,ans); 
    } 
    return 0; 
}