Cow Hurdles - 最小最大跨栏高度

题目描述/n/nFarmer John 想让她的奶牛准备郡级跳跃比赛，Bessie 和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。/n/n显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。/n/n奶牛的训练场中有 $N$ 个站台，分别标记为 $1,/dots,N$。所有站台之间有 $M$ 条单向路径，第 $i$ 条路经是从站台 $S_i$ 开始，到站台 $E_i$，其中最高的栏的高度为 $H_i$。无论如何跑，奶牛们都要跨栏。/n/n奶牛们有 $T$ 个训练任务要完成。第 $i$ 个任务包含两个数字 $A_i$ 和 $B_i$，表示奶牛必须从站台 $A_i$ 跑到站台 $B_i$，可以路过别的站台。奶牛们想找一条路径从站台 $A_i$ 到站台 $B_i$，使路径上最高的栏的高度最小。/n/n你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。/n/n## 输入格式/n/n* Line $1$: Three space-separated integers: $N$, $M$, and $T$/n* Lines $2,/dots,M+1$: Line $i+1$ contains three space-separated integers: $S_i$ , $E_i$ , and $H_i$/n* Lines $M+2,/dots,M+T+1$: Line $i+M+1$ contains two space-separated integers that describe task $i$: $A_i$ and $B_i$/n/n## 输出格式/n/n* Lines $1,/dots,T$: Line $i$ contains the result for task $i$ and tells the smallest possible maximum height necessary to travel between the stations. Output -1 if it is impossible to travel between the two stations./n/n## 样例 #1/n/n### 样例输入 #1/n/n/n5 6 3/n1 2 12/n3 2 8/n1 3 5/n2 5 3/n3 4 4/n2 4 8/n3 4/n1 2/n5 1/n/n/n### 样例输出 #1/n/n/n4/n8/n-1/n/n/n## 提示/n/n对于 $100/%$ 的数据，$1 /le N /le 300$，$1 /le M /le 2.5 /times 10^4$，$1 /le H_i /le 1 /times 10^6$，$1 /le T /le 4 /times 10^4$，$1 /le A_i,B_i /le N$。/n/n感谢 @gaozhiyong @Cppsteve 提供翻译/ncpp code内容：cpp/n#include <bits/stdc++.h>/nusing namespace std;/n/nint n, m, Q;/nconst int N = 310, M = 25100, INF = 0x3f3f3f3f;/nint h[N], e[M], ne[M], idx, w[M];/nint q[N], dist[N], cnt[N];/nbool st[N];/nint id[N], timestamp;/nint low[N], dfn[N];/n/nvoid add(int a, int b, int c) {/n e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;/n}/n/nvoid tarjan(int u) {/n low[u] = dfn[u] = ++timestamp;/n q[u] = 1, st[u] = true;/n/n for (int i = h[u]; ~i; i = ne[i]) {/n int j = e[i];/n if (!dfn[j]) {/n tarjan(j);/n low[u] = min(low[u], low[j]);/n } else if (st[j]) {/n low[u] = min(low[u], dfn[j]);/n }/n }/n/n if (dfn[u] == low[u]) {/n id[u] = ++timestamp;/n q[u] = 0;/n st[u] = false;/n }/n}/n/nbool spfa(int limit) {/n memset(dist, 0xcf, sizeof dist);/n memset(cnt, 0, sizeof cnt);/n dist[1] = 0;/n cnt[1] = 1;/n int hh = 0, tt = 0;/n q[tt++] = 1;/n while (hh != tt) {/n int t = q[hh++];/n if (hh == N) hh = 0;/n st[t] = false;/n for (int i = h[t]; ~i; i = ne[i]) {/n int j = e[i];/n if (w[i] > limit) continue;/n if (dist[j] < dist[t] + w[i]) {/n dist[j] = dist[t] + w[i];/n cnt[j] = cnt[t] + 1;/n if (cnt[j] >= n) return true;/n if (!st[j]) {/n q[tt++] = j;/n if (tt == N) tt = 0;/n st[j] = true;/n }/n }/n }/n }/n return false;/n}/n/nint main() {/n cin >> n >> m >> Q;/n memset(h, -1, sizeof h);/n while (m--) {/n int a, b, c;/n cin >> a >> b >> c;/n add(a, b, c);/n }/n/n for (int i = 1; i <= n; i++)/n if (!dfn[i])/n tarjan(i);/n/n for (int i = 0; i < idx; i++) {/n int a = e[i], b = e[i ^ 1];/n if (id[a] != id[b])/n add(id[b], id[a], w[i]);/n }/n/n while (Q--) {/n int a, b;/n cin >> a >> b;/n if (id[a] != id[b]) puts(/'-1/');/n else {/n int l = 0, r = INF;/n while (l < r) {/n int mid = l + r >> 1;/n if (spfa(mid)) r = mid;/n else l = mid + 1;/n }/n cout << l << endl;/n }/n }/n return 0;/n}/n