Berlin Programming Contest 2004 Heavy Transportation /// dijkstra oj22604

题目大意：

输入t；t为样例数

每个样例输入n，m；n 为顶点个数 m 为路径数

接下来m行  每行输入 u v w ；从 u 点到 v 点的路承重为 w 

输出 车子若想通过 1~n的最短路 车重需限制在多少之内

Sample Input

1
3 3
1 2 3
1 3 4
2 3 5

Sample Output

Scenario #1:
4

邻接阵dijkstra

重点在此式 dis[i]=max(min(dis[ind],G[ind][i]),dis[i])

即更新 dis[] 时存入的应该是max（min（本条之前路径的承重限制，当前路段的承重限制），其他路径经过该点的承重限制）

经过同条路径 各个路段的承重限制 应选较小的

经过同一个点 各条路径的承重限制 应选较大的

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
int G[1005][1005];
int vis[1005],dis[1005];
void dijk()
{
    while(1)
    {
        int maxi=-1,ind;
        for(int i=1;i<=n;i++)
            if(!vis[i] && dis[i]>maxi)
                maxi=dis[i], ind=i;
        if(maxi==-1) break;
        vis[ind]=1;
        for(int i=1;i<=n;i++)
            if(!vis[i])
                dis[i]=max(min(dis[ind],G[ind][i]),dis[i]);
    }
}
int main()
{
    int  t; scanf("%d",&t);
    for(int j=1;j<=t;j++)
    {
        scanf("%d%d",&n,&m);
        memset(vis,0,sizeof(vis));
        memset(G,0,sizeof(G));
        while(m--)
        {
            int u,v,w; 
            scanf("%d%d%d",&u,&v,&w);
            G[u][v]=G[v][u]=w;
        }

        vis[1]=1;
        for(int i=1;i<=n;i++)
            if(!vis[i]) dis[i]=G[1][i];
        dijk();
        printf("Scenario #%d:
%d

",j,dis[n]);
    }

    return 0;
}