POJ 1797 Heavy Transportation (dijkstra算法，路径中最小边的最大值)

题目意思：
n个地点，由m条街道连接， 每条街道都有一个最大重量的承重值，要求：
从1点到n点，最多能过多重的车辆。
本题要点：
1、 通俗的说，从 1点 到 n点，有很多路可走，选出其中一条路，这条路
的最短边在所有路的最短边是最大的。
2、 dijkstra 算法求单源的路径（最短边的最大值）：
a） memset(d, 0, sizeof d); 把所有路径的 d[i] 置零；
b） d[1] = INF; // 假象，从点1 到点 1，可以过重量无穷重的车辆；
c） 每次选出d[i] 值最大的 d[x], 以x点为跳板，更新x的邻接点 的 d 值;
用 min(a[x][y], d[x]) 去更新

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int INF = 0x7fffffff;
const int MaxN = 1010;
int a[MaxN][MaxN], d[MaxN], n, m, ans, T;
bool vis[MaxN];void dijkstra()
{
    memset(d, 0, sizeof d);memset(vis, false, sizeof vis);d[1] = INF;for(int i = 1; i < n; ++i){
    int x = 0; for(int j = 1; j <= n; ++j)	// 找到当前最大的 d[j]{
    if(!vis[j] && (0 == x || d[j] > d[x])){
    x = j;}}vis[x] = true;for(int y = 1; y <= n; ++y){
    if(!vis[y] && a[x][y] != 0x3f3f3f3f){
    	d[y] = max(d[y], min(a[x][y], d[x]));}}}
}int main()
{
    scanf("%d", &T);for(int t = 1; t <= T; ++t){
    memset(a, 0x3f, sizeof a);scanf("%d%d", &n, &m);for(int i = 0; i < m; ++i){
    int x, y, z;scanf("%d%d%d", &x, &y, &z);a[y][x] = a[x][y] = min(a[x][y], z);}dijkstra();printf("Scenario #%d:\n", t);printf("%d\n\n", d[n]);}return 0;
}/* 1 3 3 1 2 3 1 3 4 2 3 5 *//* Scenario #1: 4 */