2020 Multi-University Training Contest 3---- HDU--6797、Tokitsukaze and Rescue（最短路，dfs）

题面：

题意：
给定一张n个点的完全图，求删除 k 条边之后最短路的最大值，其中边权随机。
其中 $n \leq 50, k \leq m i n (n - 2, 5)$

题解：
边权随机的情况下，最短路的边数很少。
所以只要每次跑一下最短路，抓一条最短路出来，枚举删除最短路上的哪条边，然后递归，变成删
除 (k − 1) 条边的子问题。每次要删除的边一定在当前最短路上，要不然最短路不会变长。

重复这过程直到 k = 0，然后再跑一次 1 到 n 最短路，把结果取 max 即可。
复杂度 $O (n^{2} * c^{k})$ ， $c$ 为最短路边数。

$d i j$ 求最短路朴素求法是 $O (n^{2})$ 的，堆优化求法是 $O (m l o g m)$ 的，其中 $m$ 为边数，对于完全图来说，明显朴素求法更优。但是我还是比较喜欢写堆优化写法。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)>(y)?(y):(x)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxp=1100;
const int maxm=4000100;
const int up=1000;

int a[55][55],d[55],pre[55];
int n,k,ans=0;
bool ha[55];
priority_queue<pair<int,int> >q;

int dij(int s,int t)
{
    for(int i=1;i<=n;i++)
        d[i]=inf,ha[i]=false;
    while(q.size())
        q.pop();
    q.push(pr(0,s));
    d[s]=0;
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(ha[x]) continue;
        ha[x]=true;
        for(int i=1;i<=n;i++)
        {
            if(d[i]>d[x]+a[x][i])
            {
                d[i]=d[x]+a[x][i];
                q.push(pr(-d[i],i));
                pre[i]=x;
            }
        }
    }
    return d[t];
}

void dfs(int k)
{
    if(k==0)
    {
        ans=max(ans,dij(1,n));
        return ;
    }
    dij(1,n);
    vector<int>vc;
    int x=n;
    while(x)
    {
        vc.pb(x);
        x=pre[x];
    }
    for(int i=0;i<vc.size()-1;i++)
    {
        int z=a[vc[i]][vc[i+1]];
        a[vc[i]][vc[i+1]]=a[vc[i+1]][vc[i]]=inf;
        dfs(k-1);
        a[vc[i]][vc[i+1]]=a[vc[i+1]][vc[i]]=z;
    }
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d",&n,&k);
        int m=n*(n-1)/2,x,y,z;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            a[x][y]=a[y][x]=z;
        }

        ans=0;
        dfs(k);
        printf("%d\n",ans);
    }
    return 0;
}