POJ - 1797 Heavy Transportation （最短路之最大权值）

题目传送门

思路 :

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue> 
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e3+5,inf=0x3f3f3f3f;
int a[N][N],d[N],vis[N],n;//由于数据较小直接用邻接矩阵存 
#define mst(a) memset(a,0,sizeof a)
void dij(){
	priority_queue<pair<int,int> >q;//求最大值,所以是降序排列. 
	for(int i=1;i<=n;i++)
			d[i]=-inf,vis[i]=0;//后来转移时取最大值所以要取inf 
	d[1]=inf;//d[1]要初始化为inf 因为最开始取最小值. 
	q.push({d[1],1});
	while(q.size()){
		int u=q.top().second;q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int v=1;v<=n;v++)
			if(a[u][v]&&!vis[v])
				d[v]=max(d[v],min(d[u],a[u][v])),q.push({d[v],v});
	}
}
int main(){
	int t,id=0;
	scanf("%d",&t);
	while(t--){
	int m;
	scanf("%d%d",&n,&m);
		mst(a);
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		a[u][v]=a[v][u]=w;
	}
	dij();
		printf("Scenario #%d:\n%d\n\n",++id,d[n]);
	}
	return 0;
}