ABC369E

卡卡卡卡卡卡 · 2024-09-01 20:53:06 · 题解

题解

看到 N\leq 400 便考虑 floyd 来求全源最短路，求出每两个点之间的最短路。

但我们发现会有重边，便考虑取两点的最小边，取最小值。

接着是必须经过 k 条边的选择，乍一看没啥性质但观察到 k \leq 5 ，考虑暴力枚举走边的顺序，最后算下来只有 2^kk!，可以通过。

时间复杂度：\mathcal O(2^kk! + N^3)。

#include<bits/stdc++.h>
using namespace std;
long long a[505][505],k,p[50005],ans=1e18,bz[500005];
long long n,m;
struct edge
{
    long long u,v,w;
}e[500005];
void dfs(long long t,long long sum,long long now)
{
    if(t==k+1)
    {
        ans=min(ans,sum+a[now][n]);
        return ;
    }
    for(int i=1;i<=k;i++)
    {
        if(bz[i]==0)
        {
            bz[i]=1;
            dfs(t+1,sum+a[now][e[p[i]].u]+e[p[i]].w,e[p[i]].v);
            dfs(t+1,sum+a[now][e[p[i]].v]+e[p[i]].w,e[p[i]].u);
            bz[i]=0;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            a[i][j]=1e18;
        }
    for(int i=1;i<=n;i++)a[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].u>>e[i].v>>e[i].w,a[e[i].u][e[i].v]=min(e[i].w,a[e[i].u][e[i].v]),a[e[i].v][e[i].u]=min(a[e[i].v][e[i].u],e[i].w);
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]>(a[i][k]+a[k][j])) a[i][j]=a[i][k]+a[k][j];
            }
    long long q;
    cin>>q;
    while(q--)
    {
        ans=1e18;
        cin>>k;
        for(int i=1;i<=k;i++)cin>>p[i];
        dfs(1,0,1);
        cout<<ans<<'\n';
    }
}