POJ - 1797 Heavy Transportation (Dijkstra)

POJ - 1797 Heavy Transportation

题意经过路径的最小值，中的最大权值

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int e[1010][1010];
bool vis[1010];
int dis[1010];
int t,n,m;
void dijkstra()
{
    memset(vis,0,sizeof vis);for(int i=1;i<=n;i++) dis[i]=e[1][i];dis[1]=0;for(int i=1;i<n;i++){
    int u=-1;for(int j=1;j<=n;j++)if(!vis[j]&&(u==-1||dis[u]<dis[j]))u=j;vis[u]=true;for(int j=1;j<=n;j++)dis[j]=max(dis[j],min(dis[u],e[u][j]));}
}
int main(void)
{
    cin>>t;for(int i=1;i<=t;i++){
    memset(e,0,sizeof e);cin>>n>>m;while(m--){
    int a,b,c;cin>>a>>b>>c;e[a][b]=e[b][a]=c;}dijkstra();printf("Scenario #%d:\n",i);printf("%d\n",dis[n]);puts("");}return 0;
}