<题目链接>
题目大意：
Hugo Heavy要从城市1到城市N运送货物，有M条道路，每条道路都有它的最大载重量，问从城市1到城市N运送最多的重量是多少。
解题分析：
感觉这道题用dijkstra不是很好想，有点抽象。我反而觉得这道题用最大流比较好想，比如EK算法，用BFS求出所有1->n的增广路径，然后求出每条增广路径的最小值，就可最终得到这些最小值中的最大值。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
#define MAXV 1010
#define INF 0x3f3f3f3f
int map[MAXV][MAXV],n,m; int dijkstra(){
int vis[MAXV],d[MAXV],i,j,v; memset(vis,,sizeof(vis));
for(int i=;i<=n;i++){ //注意这个初始化
d[i]=map[][i];`
}
int cur=;
for(int i=;i<=n;i++){
vis[cur]=;
for(int j=;j<=n;j++){
if(!vis[j]&&d[j]<min(d[cur],map[cur][j])){ //仔细揣摩这里，本题的关键
d[j]=min(d[cur],map[cur][j]);
}
} int cal=-INF,loc=-;
for(int j=;j<=n;j++){
if(!vis[j]&&d[j]>cal){
loc=j;
cal=d[j];
}
}
cur=loc;
} return d[n];
} int main(){
int t,i,j,kcase,a,b,c;
scanf("%d",&kcase);
for(t=;t<=kcase;t++)
{
scanf("%d %d",&n,&m);
memset(map,,sizeof(map)); for(i=;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
map[a][b]=map[b][a]=c;
}
printf("Scenario #%d:\n",t);
printf("%d\n\n",dijkstra());
}
return ;
}
2018-08-15