在郊区有 N 座通信基站，P 条双向电缆，第 i 条电缆连接基站Ai和Bi。特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。现在，农场主希望对通信线路进行升级，其中升级第 i 条电缆需要花费Li。电话公司正在举行优惠活动。农产主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。求至少用多少钱可以完成升级。
输入格式 第1行：三个整数N，P，K。 第2…P+1行：第 i+1 行包含三个整数Ai,Bi,Li。
输出格式 包含一个整数表示最少花费。 若1号基站与N号基站之间不存在路径，则输出”-1”。
数据范围 0≤K<N≤1000, 1≤P≤10000, 1≤Li≤1000000
输入样例： 5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6 输出样例： 4看到题目第一反应是深搜，结果13个测试点通过3个，超时。
#include <bits/stdc++.h> using namespace std; int N, P, K; bool compare(int x1, int x2) { return x1 > x2; } int walk_through[10001]; vector<int> base_station[1001][2]; int caust[10001]; int caust_i; int min_caust = 0x3f3f3f3f; int caust0[10001]; int dfs(int x) { for (int i = 0; i < base_station[x][0].size(); i++) { if (base_station[x][0][i] == N) { caust[caust_i] = base_station[x][1][i]; caust_i++; for (int k = 0; k < caust_i; k++) caust0[k] = caust[k]; sort(caust0, caust0 + caust_i, compare); if (K >= caust_i) return 0; else { if (caust0[K] < min_caust) min_caust = caust0[K]; } } else if (walk_through[base_station[x][0][i]] == 0) { int old_caust_i = caust_i; walk_through[base_station[x][0][i]] = 1; caust[caust_i] = base_station[x][1][i]; caust_i++; dfs(base_station[x][0][i]); caust_i = old_caust_i; walk_through[base_station[x][0][i]] = 0; } } return min_caust; } int main() { cin >> N >> P >> K; for (int i = 1; i <= P; i++) { int A, B, L; cin >> A >> B >> L; base_station[A][0].push_back(B); base_station[A][1].push_back(L); base_station[B][0].push_back(A); base_station[B][1].push_back(L); } int ans = dfs(1); if (ans == 0x3f3f3f3f) cout << -1; else cout << ans; return 0; }spfa+动态规划实现维护到达每一个节点的最佳路径所经过的边中前k+1大的项组成的递减序列。 这里dp[x][ki]的含义为：对于从节点1出发到达x的所有路径中的前k+1大的边放在一起排序，取前k+1小的边中第ki+1大的边。
#include <bits/stdc++.h> using namespace std; int dp[1001][1001]; vector<int> edge[1001][2]; bool visit[1001]; int N, P, K, flag; void spfa() { memset(visit, false, sizeof(visit)); memset(dp, 0x3f, sizeof(dp)); dp[1][0] = 0; queue<int> q; q.push(1); visit[1] = true; while (!q.empty()) { int x = q.front(); if (x == N) flag = 1; q.pop(); visit[x] = false; for (int i = 0; i < edge[x][0].size(); i++) { int y = edge[x][0][i], z = edge[x][1][i], w = max(dp[x][0], z); if (dp[y][0] > w) { dp[y][0] = w; if (!visit[y]) { q.push(y); visit[y] = true; } } for (int p = 1; p <= K; p++) { int v = min(dp[x][p - 1], max(dp[x][p], z)); if (dp[y][p] > v) { dp[y][p] = v; if (!visit[y]) { q.push(y); visit[y] = true; } } } } } } int main() { cin >> N >> P >> K; for (int i = 1; i <= P; i++) { int A, B, L; cin >> A >> B >> L; edge[A][0].push_back(B); edge[A][1].push_back(L); edge[B][0].push_back(A); edge[B][1].push_back(L); } spfa(); if(flag) cout<<dp[N][K]; else cout<<-1; return 0; }