题意：Hugo Heavy要从城市1到城市N运送货物，有M条道路，每条道路都有它的最大载重量，问从城市1到城市N运送最多的重量是多少。

求一个图中能通过最大重量：

求s到t的可行路径上最小值的最大值（有点拗口啊）也就是说从s到t的每一条可行路径上都有一条最小权值（可负载的重量）的边，如果有多条路径的话就求这些最小值的最大值。

if(dis[j] < min{dis[i],graph[i][j]} dis[j] = min{dis[i],graph[i][j]}

其中dis【i】表示从1到i的所有路径上权值最小的边的最大值。

由于是要求最大值，因此第一次取最大节点。以后也应该去最大节点。

假设w[i,j]权值为4，d[j]=3，d[i]=5（表示从源点到点i的所有路径中最小权值的最大的为5，假设该路径为5,6,7,8,10）。当d[j]小于min{dis[i],graph[i][j]}，说明有更行的必要，因为从源点到j点还可以承受更大的流量，从源点到i点再到j点的路径可以是(4,5,6,7,8,10)，因此最大流从3变成了4.0

DIJ算法是每次将最短的点加入集合中（加入集合的顶点本身就已经满足了最短路要求，不用再被更新）。这里是将最大的点加入集合中。根据DIJ算法的证明，假设u是第一个接受了不正确的d值，即d[u]>δ(s,u).

假设y是u前趋，y接受了正确的d值（因为u是第一个不正确的，x已经加入集合，值不会被改变，因此一定是正确的，根据松弛性质，y的值一定是正确的），所有d[y]=δ(s,y)<=δ(s,u).<=d[u].

而在从未标记的点中选择最小的时候（此时u,y均未被选） 选择的是u节点，所有d[u]<=d[y]，因此得出矛盾，所以d[u]=δ(s,u).

这里u,y并存时，考虑的是先取u，如果先取y,则是按照最短路的顺序来取，那得到的一定是正确的。

这里的问题，设x,y,u是所需要求的最大流路径，每次选择最大的节点，因此d[u]>=d[y],但d[y]>=d[u].（因为先求d[u]，后求d[y]，后求的可能会变大），得出矛盾，因此一样正确。

#include<stdio.h>

int net[1005][1005];

int dis[1005],flag[1005];

int n,m;

int min(int a,int b)

{

return a<b?a:b;

}

void Dijkstra()

{

int i,j,w;

int max;

dis[0]=0;

for(i=1;i<n;i++)

{

dis[i]=net[0][i];

flag[i]=0;

}//初始化

flag[0]=1;

for(i=0;i<n-1;i++)

{

max=0;

w=0;

for(j=1;j<n;j++)

{

if(flag[j]==0 && dis[j]>max)

{

w=j;

max=dis[j];

}

}//找出第一个比较大的权重

if(w==0)

break;

flag[w]=1;

for(j=1;j<n;j++)

{

if(flag[j]==0 && dis[j]<min(dis[w],net[w][j]))

dis[j]=min(dis[w],net[w][j]);

}//在路径上更新权重，不同于传统的Dis传统得为权重之和

}

}

int main()

{

int i,j;

int count;

int u,v,dist,Case;

    scanf("%d",&count);

for(Case=1;Case<=count;Case++)

{

scanf("%d%d",&n,&m);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

net[i][j]=0;

}//初始化图

for(i=1;i<=m;i++)

{

scanf("%d%d%d",&u,&v,&dist);

net[u-1][v-1]=dist;

net[v-1][u-1]=dist;

}//构建图

Dijkstra();

printf("\nScenario #%d:\n%d\n\n",Case,dis[n-1]);

}

return 0;

}