题目链接：http://www.ifrog.cc/acm/problem/1126
1126 - 咸鱼旅行Time Limit：3s Memory Limit：128MByte
Submissions：580Solved：110
DESCRIPTION这个地区可以看作是一个无向图，N个点M条边组成。每个边有一个边权。我们定义一条路径的花费，就是这条路径上最大的边权。 现在有一条咸鱼，想从S走到T，徒步旅行。 咸鱼于是找到了你，想让你告诉他从S到T的最小花费。
INPUT 第一行两个整数，N,M。满足(1 <= N <= 10^5, 0 <= M <= 5*10^5)接下来M行，每行三个整数U,V,C。表示有一个连接U点和V点的边，且边权是C。(1<=C<=10^9)接下来一个行是两个整数S,T(1<=S,T<=n) OUTPUT 输出答案，如果S不能到达T，输出-1 SAMPLE INPUT 5 5 1 2 1 2 3 1 3 4 1 4 5 1 5 1 1 1 3 SAMPLE OUTPUT 1 SOLUTION “玲珑杯”ACM比赛 Round #15 Submit summary Discuss解析：最短路问题，最大路径最小值，吃两次亏了，一次是2017-3-19 CCF D题写错成有向图（再加一条路径变成无向图就能得100分，结果20分），另外一次就是2017-5-27 蓝桥杯国赛第四题判断有无环，输出环所在的节点（又是硬生生的给写成有向图），这次玲珑杯河南专场，就算所有题都不写，也要过这个题，真是气人
代码：
#include<bits/stdc++.h> #define N 100009 using namespace std; struct node { int v, w; }; vector<node> T[N]; typedef pair<int, int> P; inline void q_read(int &num) { int f = 1; char ch; while(true) { ch = getchar(); if(ch == '-') f = -1; if(isdigit(ch)) { num = ch - '0'; break; } } while(ch = getchar(), isdigit(ch)) num = num * 10 + ch - '0'; num *= f; } int solve(int n, int S, int TT) { int d[N]; memset(d, 0x3f, sizeof(d)); priority_queue<P, vector<P>, greater<P> > q; d[S] = 0; q.push(P(0, S)); while(!q.empty()) { P p = q.top(); q.pop(); int v = p.second; if(d[v] < p.first) continue; for(int i = 0; i < T[v].size(); i++) { node &e = T[v][i]; if(d[e.v] == 0x3f3f3f3f || d[e.v] > max(d[v], e.w)) { d[e.v] = max(d[v], e.w); q.push(P(d[e.v], e.v)); } } } return d[TT] == 0x3f3f3f3f ? -1: d[TT]; } int main() { int n, m, u, v, w, S, TT; q_read(n); q_read(m); for(int i = 1; i <= m; i++) { //scanf("%d%d%d", &u, &v, &w); q_read(u); q_read(v); q_read(w); T[u].push_back((node){v, w}); T[v].push_back((node){u, w}); } //scanf("%d%d", &S, &TT); q_read(S); q_read(TT); int ans = solve(n, S, TT); printf("%d\n", ans); return 0; }
