题解：AT_abc369_e [ABC369E] Sightseeing Tour

zibenlun · 2024-09-02 08:54:09 · 题解

思路

看到 n 的范围很小，所以能够用 Floyd 跑出所有点之间的最短路。看到每一次询问，我们将经过 k 条边转化为依次经过 k+k 个点，当然在一条边上的点必须相邻，所以可以将所有的边全排列，并枚举先经过每一条边上的哪一个点，求一个最小值即可。

代码

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
#define faster ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
struct nd{
    int x,y,z;
}a[200005];
int b[105];
int dp[505][505];
int n,m,q,k;
signed main() {
    faster
    cin>>n>>m;memset(dp,0x3f,sizeof dp);
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        a[i]={x,y,z};
        dp[x][y]=min(dp[x][y],z);
        dp[y][x]=min(dp[y][x],z);
    }
    for(int i=1;i<=n;i++){
        dp[i][i]=0;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>k;
        int ans=1e18;
        for(int j=1;j<=k;j++){
            cin>>b[j];
        }sort(b+1,b+1+k);
        do  {
            for(int u=0;u<(1<<k);u++){
                // cout<<1;
                int vis[10]={0},o=u;
                for(int j=1;j<=k;j++){
                    if(o&1) vis[j]=1;
                    o>>=1;
                }
                int pos=1,sum=0;
                for(int j=1;j<=k;j++){
                    if(vis[j]==0){
                        sum+=dp[pos][a[b[j]].x]+a[b[j]].z;pos=a[b[j]].y;
                    }
                    else {
                        sum+=dp[pos][a[b[j]].y]+a[b[j]].z;pos=a[b[j]].x;
                    }
                }
                ans=min(ans,sum+dp[pos][n]);
            }
        }while(next_permutation(b+1,b+1+k));  
        cout<<ans<<"\n";
    }
    return 0;
}