(dijkstra記録経路)find the longest of the shortest

MaricaはMirkoに怒っていた.彼は新しい彼女を見つけたので、彼女は復讐したいと思っていた.彼女は同じ町に住んでいないので、長距離旅行の準備を始めました.私たちはそれぞれの道が一つの都市から別の都市まで何分かかるか知っています.
ミルコは車の中で何気なくその中の1つの道が修理されているのを聞いて、道が塞がれているが、具体的にはどの道なのか分からない.どの道が閉鎖されていても、マリカの都市からミルコまでは可能です.
マリカは渋滞しない道だけを歩いて、しかも一番短い道を歩いています.ミルコは彼女が最悪の状況でどのくらい彼の都市に着くことができるかを知りたいと思っています.そうすれば、彼は彼女がこの都市を離れるのに十分な時間を確保することができます.MirkoがMaricaが渋滞していない道路から彼の都市までの最短ルートを見つけるのに必要な数分で最も長い時間を見つけるのを助けるプログラムを作成します.
入力
いずれの場合も1行目に2つの数字があり、NとMは、1つの個別の空間、都市の数、都市との間の道路の数から分かれています.1≤N≤1000,1≤≤N *(N - 1)/2.これらの都市の番号は1からN、Mirkoは都市1、Maricaは都市Nにある.
次のM行は、カンマで区切られた3つの数字A、B、Vです.1≤B≤N 1 V≤≤1000.これらの数字は、aとB都市の間に双方向の道路があり、V分以内に交差できることを意味している.
しゅつりょく
出力ファイルの最初の行に最大時間を分単位で書き込むと、MaricaはMirkoに到達するのに数分かかる場合があります.
サンプル入力
5 6
1 2 4
1 3 3
1 2 3
2 4 4
2 5 7
4 5 1
6 7 1 2 1
2 3 4
3 4 4
4 6 4
1 5 5
2 5 2
5 6 5
5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10
サンプル出力
11
13
27
最短とは、時間が最も短く、1つのエッジが壊れていることを意味します.このときの最短の時間は、他の1つのエッジが壊れた後の最短の時間よりも長く、この時間を出力します
分析と解答
取り外したエッジが最初の最短路にないと、最短路の長さは変化しません.では、最短ルートのエッジだけ取り外します.(上の文の参考:http://blog.sina.com.cn/s/blog_8d84b9240101f827.html)これで私たちが分解する範囲が小さくなり、どのように分解と言えるのか、2つの道の距離をinfにすればいいのです.取り外したのは最短ルート上のエッジなので、最短ルートも記録します.取り外しが終わったらdijkstraを呼び出します.この場合、最短のパスを記録する必要はありません.また、次の別の道を取り外すために、取り外した道を復元する必要があります.
パスを記録する方法を見てみましょう.

for(j=1;j<=m;j++)
if(!vis[j]&&dis[k]+map[k][j][j])
        {
            dis[j]=dis[k]+map[k][j];
            p[j]=k;//p       ， j   
        }   

始点から終点kまでの最短距離dis[k]を見つけ、現在kを始点として他の点を終点とする最短距離dis[j]を更新している.
コード参照:https://blog.csdn.net/z8110/article/details/50061289

#include
#include
#include
#define N 0x3f3f3f3f
using namespace std;
int map[1100][1100],dis[1100],vis[1100],i,j,k,l,m,n,x,y,z,p[1100];
void dj(int v)//        
{
    int i,j,k;
    memset(vis,0,sizeof(vis));
    memset(dis,N,sizeof(dis));
    dis[1]=0;//           
    for(i=1;i<=m;i++)
    {
        int Min=N;
        for(j=1;j<=m;j++)
        {
            if(!vis[j]&&dis[j]if(Min==N)//  ，         ，     
        return ;
        vis[k]=1;
        for(j=1;j<=m;j++)
        if(!vis[j]&&dis[k]+map[k][j]map[k][j];
            if(v)
            p[j]=k;//p       ， j   
        }   
    }
}
int main()
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(p,0,sizeof(p));
        memset(map,N,sizeof(map));
//        for(i=1;i<=m;i++)
//        map[i][i]=0;
        for(i=0;iscanf("%d%d%d",&x,&y,&z);
            if(map[x][y]>z)
            map[x][y]=map[y][x]=z;
        }
        //int ans=dj(1);
        //printf("++%d
",ans);
        dj(1);// 1    
        int Max=dis[m];
        for(i=m;i!=1;i=p[i])// m     p[j]=k k  j，   m 
        {
            z=map[i][p[i]];//                    
            map[i][p[i]]=map[p[i]][i]=N;
            dj(0);//          ，          
            Max=max(Max,dis[m]); 
            map[i][p[i]]=map[p[i]][i]=z;//    
        }
        printf("%d
",Max);
    }
}