网上的题解都是分层图+spfa或者dijkstra
我觉得dijk太难写了，懒得写，看了一下数据范围$N=50$，这显然是出题人勾引人犯罪
我决定使用floyd的做法，令$f[i][j][t](k)$表示路径$i$到$j$上，最大的节点编号为$k$，且使用了$t$次加速以后的最短路径长度，转移方程显而易见
同时这个时间复杂度是$O(N^5)$，大约在3亿左右，我们知道floyd的常数很小很小，而时限有3秒，显然是可以过的
最后floyd用了500ms，而dijk用了4ms，差不多差不多.jpg
但是floyd可好写了
1 /************************************************************** 2 Problem: 2662 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:520 ms 7 Memory:1472 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 13 using namespace std; 14 const int N = 55; 15 16 int n, m, K; 17 int f[N][N][N]; 18 int ans; 19 20 inline int min(int x, int y) { 21 return x < y ? x : y; 22 } 23 24 int main() { 25 int x, y, z; 26 scanf("%d%d%d", &n, &m, &K); 27 memset(f, 0x3f, sizeof(f)); 28 for (int i = 1; i <= m; ++i) { 29 scanf("%d%d%d", &x, &y, &z); 30 f[x][y][0] = f[y][x][0] = z; 31 f[x][y][1] = f[y][x][1] = z / 2; 32 } 33 for (int k = 1; k <= n; ++k) 34 for (int i = 1; i <= n; ++i) 35 for (int j = 1; j <= n; ++j) 36 for (int p = 0; p <= K; ++p) 37 for (int q = 0; q <= p; ++q) { 38 f[i][j][p] = min(f[i][j][p], f[i][k][q] + f[k][j][p - q]); 39 } 40 ans = 1e9; 41 for (int p = 0; p <= K; ++p) 42 ans = min(ans, f[1][n][p]); 43 printf("%d ", ans); 44 return 0; 45 } 46