题目链接
题意：
节点数n<=50的完全图，去掉k条边( 最大为5 ) 之后，1-n的最短路的最大值是多少?
思路：
dfs暴力
完全图，随机的数据，大体可以猜测最短路不会太长，所以只要每次跑一下最短路，取一条最短路出来，枚举删除最短路上的一条边，然后递归，变成删除 (k ? 1) 条边的子问题。
#include <iostream>
#include <cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=52;
int d[maxn][maxn];
int n,k;
int ans;
int dis[maxn];
int f[maxn][maxn];
int vis[maxn];
void dfs(int k) {for (int i = 1; i <= n; i++) {dis[i] = inf;vis[i] = 0;f[k][i] = 0;}dis[1] = 0;for (int i = 1; i <= n; i++) {int v = 0;for (int j = 1; j <= n; j++) {if (!vis[j]) {if (!v || dis[v] > dis[j]) v = j;}}vis[v] = 1;for (int j = 1; j <= n; j++) {if (!vis[j] && dis[v] + d[v][j] < dis[j]) {dis[j] = dis[v] + d[v][j];f[k][j] = v;}}}if (!k) {ans = max(ans, dis[n]);return;}int j;for (int i = n; i > 1; i = j) {j = f[k][i];int tmp = d[i][j];d[i][j] = d[j][i] = inf;dfs(k - 1);d[i][j] = d[j][i] = tmp;}
}
void work() {scanf("%d%d", &n, &k);for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) d[i][j] = 0; else d[i][j] = inf;}}for (int i = 1, u, v, w; i <= n * (n - 1) / 2; i++) {scanf("%d%d%d", &u, &v, &w);d[u][v] = d[v][u] = w;}ans=0;dfs(k);printf("%d\n", ans);
}
int main() {int _;scanf("%d", &_);while (_--) {work();}return 0;
}