Tokitsukaze and Rescue----------------------思维(spfa+dfs)

题意:
给定n个点的完全图，你可以删除k条边，使得最短路最长

解析:
由于k最大为5，所以我们可以采用dfs。
我们只要删除最短路径中的任意一条路经即可(dfs枚举删除路经即可) 然后就递归到下一层删除(k-1)条边的子问题。

用一个path数组记录最短路径

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+1000;
int t,n,k,u,v,c;
int path[N],g[100][100];
int dist[N],st[N];
int ans;
void spfa()
{
   for(int i=0;i<=1000;i++) dist[i]=0x3f3f3f3f,path[i]=0,st[i]=false;
    queue<int> q;
    q.push(1);
    st[1]=true;
    dist[1]=0;
    while(q.size())
    {
        auto t= q.front();q.pop();
        st[t]=false;
        for(int i=1;i<=n;i++){
            int v=g[t][i];
            if(!v) continue;
            if(dist[i]>dist[t]+v){
                dist[i]=dist[t]+v;
                 path[i]=t;
                if(!st[i]){
                    st[i]=true;
                    q.push(i);
                }
            }
        }
    }
}
void dfs(int u)
{
    spfa();

    if(u==0) {

        ans=max(ans,dist[n]);
        return ;
    }
    int num=0;
    int p[1000];
    p[++num]=n;
    int j=n;
    while(path[j]){

        p[++num]=path[j];
        j=path[j];
    }

    for(int i=1;i<num;i++){
        int val=g[p[i]][p[i+1]];
        g[p[i]][p[i+1]]=g[p[i+1]][p[i]]=0;
        dfs(u-1);
        g[p[i]][p[i+1]]=g[p[i+1]][p[i]]=val;
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&k);
        ans=0;

        for(int i=1;i<=(n*(n-1))/2;i++)
        {
            scanf("%d %d %d",&u,&v,&c);
            g[u][v]=g[v][u]=c;
        }
        dfs(k);
        printf("%d\n",ans);
    }
    return 0;
}