洛谷题解-P2888 [USACO07NOV] Cow Hurdles S （Floyd）

https://www.luogu.com.cn/problem/P2888

题目描述

Farmer John wants the cows to prepare for the county jumping competition, so Bessie and the gang are practicing jumping over hurdles. They are getting tired, though, so they want to be able to use as little energy as possible to jump over the hurdles.

Obviously, it is not very difficult for a cow to jump over several very short hurdles, but one tall hurdle can be very stressful. Thus, the cows are only concerned about the height of the tallest hurdle they have to jump over.

The cows' practice room has NNN stations, conveniently labeled 1,…,N1,\dots,N1,…,N. A set of MMM one-way paths connects pairs of stations; the paths are also conveniently labeled 1,…,M1,\dots,M1,…,M. Path iii travels from station SiS_iSi​ to station EiE_iEi​ and contains exactly one hurdle of height HiH_iHi​. Cows must jump hurdles in any path they traverse.

The cows have TTT tasks to complete. Task iii comprises two distinct numbers, AiA_iAi​ and BiB_iBi​, which connote that a cow has to travel from station AiA_iAi​ to station BiB_iBi​ (by traversing over one or more paths over some route). The cows want to take a path the minimizes the height of the tallest hurdle they jump over when traveling from AiA_iAi​ to BiB_iBi​ . Your job is to write a program that determines the path whose tallest hurdle is smallest and report that height.

Farmer John 想让她的奶牛准备郡级跳跃比赛，Bessie 和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。 显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。

奶牛的训练场中有 NNN 个站台，分别标记为 1,…,N1,\dots,N1,…,N。所有站台之间有 MMM 条单向路径，第 iii 条路经是从站台 SiS_iSi​ 开始，到站台 EiE_iEi​，其中最高的栏的高度为 HiH_iHi​。无论如何跑，奶牛们都要跨栏。

奶牛们有 TTT 个训练任务要完成。第 iii 个任务包含两个数字 AiA_iAi​ 和 BiB_iBi​，表示奶牛必须从站台 AiA_iAi​ 跑到站台 BiB_iBi​，可以路过别的站台。奶牛们想找一条路径从站台 AiA_iAi​ 到站台 BiB_iBi​，使路径上最高的栏的高度最小。 你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。

输入格式

* Line 111: Three space-separated integers: NNN, MMM, and TTT

* Lines 2,…,M+12,\dots,M+12,…,M+1: Line i+1i+1i+1 contains three space-separated integers: SiS_iSi​ , EiE_iEi​ , and HiH_iHi​

* Lines M+2,…,M+T+1M+2,\dots,M+T+1M+2,…,M+T+1: Line i+M+1i+M+1i+M+1 contains two space-separated integers that describe task iii: AiA_iAi​ and BiB_iBi​

第一行：三个空格隔开的整数 N,M,TN, M, TN,M,T。

接下来 MMM 行：第 iii 行包含三个空格隔开的整数 Si,Ei,HiS_i, E_i, H_iSi​,Ei​,Hi​。

接下来 TTT 行：第 iii 行包含两个空格隔开的整数，表示任务 iii 的起始站台和目标站台 Ai,BiA_i, B_iAi​,Bi​。

输出格式

* Lines 1,…,T1,\dots,T1,…,T: Line iii contains the result for task iii 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.

TTT 行：第 iii 行为一个整数，表示任务 iii 路径上最高的栏的高度的最小值。如果无法到达，输出 -1。

输入输出样例

5 6 3
1 2 12
3 2 8
1 3 5
2 5 3
3 4 4
2 4 8
3 4
1 2
5 1

4
8
-1

说明/提示

对于 100%100\%100% 的数据，1≤N≤3001 \le N \le 3001≤N≤300，1≤M≤2.5×1041 \le M \le 2.5 \times 10^41≤M≤2.5×104，1≤Hi≤1×1061 \le H_i \le 1 \times 10^61≤Hi​≤1×106，1≤T≤4×1041 \le T \le 4 \times 10^41≤T≤4×104，1≤Ai,Bi≤N1 \le A_i,B_i \le N1≤Ai​,Bi​≤N。

感谢 @gaozhiyong @Cppsteve 提供翻译

这题一看就是多源多汇，所以考虑floyd，但求得不是最短路，而是最短路上面的每条边最大值中的最小值

Floyd不仅仅可以求最短路，他的状态转移方程改一改还可以求别的东西

#include <bits/stdc++.h>
using namespace std;

const int N=305;
int n, m, t, u1, v1, w1, dis[N][N], x, y;
int main()
{
	memset(dis, 63, sizeof dis);
	
	scanf("%d%d%d", &n, &m, &t);
	for (int i=1; i<=m; i++)
	{
		scanf("%d%d%d", &u1, &v1, &w1);
		dis[u1][v1]=min(dis[u1][v1], w1);
		dis[u1][u1]=0, dis[v1][v1]=0;
	}
	for (int k=1; k<=n; k++)
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
				dis[i][j]=min(dis[i][j], max(dis[i][k], dis[k][j])); //改一下状态转移方程也可以过此题，意思是i->k，k->j的路径中取最高的栏，然后再和i->j的路径取个最小值，使最大值最小
	
	for (int i=1; i<=t; i++)
	{
		scanf("%d%d", &x, &y);
	
		if (dis[x][y]==dis[0][0]) printf("-1\n");
		else printf("%d\n", dis[x][y]);
	}
	return 0;
}