CCF CSP 201703-4 地铁修建（Dijkstra）

思路：

题意即求结点1到结点n的所有路径中，边权的最大值最小的那条路径的边权最大值，稍微改用一下Dijkstra即可；

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAX_V=1e5+99;
const int INF=1<<30;
struct edge{int to,cost;};
typedef pair<int,int> P;
int n,m,d[MAX_V];
vector<edge> G[MAX_V];
void dijkstra(int s){
	priority_queue<P,vector<P>,greater<P> > que;
	fill(d+1,d+n+1,INF);
	d[s]=0;
	que.push(P(0,s));
	while(!que.empty()){
		P p=que.top(); que.pop();
		int v=p.second;
		if(d[v]<p.first) continue;
		for(edge e:G[v]){
			if(d[e.to]>max(e.cost,d[v])){
				d[e.to]=max(e.cost,d[v]);
				que.push(P(d[e.to],e.to));
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
//	freopen("Illya.txt","r",stdin);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b,c; cin>>a>>b>>c;
		G[a].push_back(edge{b,c});
		G[b].push_back(edge{a,c});
	}
	dijkstra(1);
	cout<<d[n];
	return 0;
}