> 核心:
> double Dijk(int a,int b)
> {
>     for(int i=1;i<=N;i++) {M[i]=G[a][i];inq[i]=0;}
>     M[a]=0,inq[a]=1;
>     for(int I=1;I<N;I++)
>     {
>         double Minn=100000000;
>         int Min;
>         for(int i=1;i<=N;i++)
>         {
>             if(!inq[i] && M[i]<Minn)
>             {
>                 Minn=M[i];
>                 Min=i;
>             }
>         }
>         inq[Min]=1;
>         for(int i=1;i<=N;i++)
>             if(!inq[i] && G[Min][i]<100000000)
>                 if(M[Min]+G[Min][i]<M[i])
>                     M[i]=M[Min]+G[Min][i];
>     }
>     return M[b];
> }
> 这一题用了一个改版,其中M数组记录松弛过程中的一个边,我们可以想到因为以后的每次松弛都会沿用原来松弛的某个边,于是我们可以用一个变量记录松弛中的最大边,最后返回它就行了.
> 改版:
> double Dijk(int a,int b)
> {
>     for(int i=1;i<=N;i++) {M[i]=G[a][i];inq[i]=0;}
>     M[a]=0,inq[a]=1;
>     double Maxn=0;
>     for(int I=1;I<N;I++)
>     {
>         double Minn=100000000;
>         int Min;
>         for(int i=1;i<=N;i++)
>         {
>             if(!inq[i] && M[i]<Minn)
>             {
>                 Minn=M[i];
>                 Min=i;
>             }
>         }
>         if(Minn>Maxn) Maxn=Minn;
>         if(Min==b)
>             return Maxn;
>         inq[Min]=1;
>         for(int i=1;i<=N;i++)
>             if(!inq[i] && G[Min][i]<100000000)
>                 if(G[Min][i]<M[i])
>                     M[i]=G[Min][i];
>     }
> }