2018 宁夏 F. Moving On

给个图，有边权和点权，多组询问只能经过点权小于等于K的点的 两点之间的最短距离

先将点按照点权排序，从小到大枚举每个点作为中间的点，跑 floyd ，询问只需要找到最大的小于等于K的点权的那层图，直接输出就可以。

https://nanti.jisuanke.com/t/41290

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
#define Pair pair<int,int>
Pair a[100000];
ll dp[205][205][205];
int b[205];
int n, q;
void Flody()
{
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][a[k].first] + dp[k - 1][a[k].first][j]);
			}
		}
	}
}
int main()
{
	int T, cas = 1;
	sc("%d", &T);
	while (T--)
	{
		pr("Case #%d:\n", cas++);
		sc("%d%d", &n, &q);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				for (int k = 1; k <= n; k++)
					dp[i][j][k] = 1e9 + 7;
		for (int i = 1; i <= n; i++)
		{
			a[i].first = i;
			sc("%d", &a[i].second);
		}
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				sc("%d", &dp[0][i][j]);
		sort(a + 1, a + n + 1, [](Pair q, Pair w) {
			return q.second < w.second;
		});
		for (int i = 1; i <= n; i++)
			b[i] = a[i].second;
		Flody();
		while (q--)
		{
			int u, v, k;
			sc("%d%d%d", &u, &v, &k);
			k = upper_bound(b + 1, b + 1 + n, k) - b - 1;
			pr("%lld\n", dp[k][u][v]);
		}
	}
}