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]); } } }