学步园

题意是要我们求出最短路中一条路坏的情况下最大的时间；

我们先将最短路求出并记录路径，然后枚举最短路中每一条路坏的情况，求出最大的时间。。

<span style="font-size:24px;">#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int s[1005][1005];
int p[1005];
int vist[1005];
int q[1005];
const int inf = 1000000000;
int a,b;
int djs(int v)
{
    int poit=0;
    memset(vist,0,sizeof(vist));
    for(int i=1;i<=a;i++)
        q[i]=inf;
    q[1]=0;
    for(int j=1;j<=a;j++)
    {
        int min1=inf;
        for(int i=1;i<=a;i++)
        {
            if(!vist[i]&&q[i]<min1)
            {
                min1=q[i];
                poit=i;
            }
        }
        vist[poit]=1;
        for(int i=1;i<=a;i++)
        {
            if(!vist[i]&&q[i]>(q[poit]+s[poit][i]))
            {
                q[i]=q[poit]+s[poit][i];
               <u> if(v)</u>
                    p[i]=poit;
            }
        }
    }
    return q[a];
}
int main()
{
    int c,d,e;
    while(~scanf("%d %d",&a,&b))
    {
        memset(p,0,sizeof(p));
        for(int i=1;i<=a;i++)
            for(int j=1;j<=a;j++)
             if(i==j)
                s[i][j]=0;
            else
                s[i][j]=inf;
        for(int i=0;i<b;i++)
        {
           scanf("%d %d %d",&c,&d,&e);
           if(s[c][d]>e) s[c][d]=s[d][c]=e;
        }
        int ans=djs(1);
        for(int i=a;i!=1;i=p[i])
        {
            int t=s[i][p[i]];
            s[i][p[i]]=inf;
            s[p[i]][i]=inf;
            int tt=djs(0);//djs中是0是不再次记录路径
            if(ans<tt)
                ans=tt;
            s[i][p[i]]=t;
            s[p[i]][i]=t;
        }
        printf("%d\n",ans);
    }
    return 0;
}
</span>