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