Question

ABC338 F Negative Traveling Salesman

给出一个 \(N\) 个点 \(M\) 条边的有向图，边权可能为负数，但不可能有负环

每经过一条边就要加上这条边的代价

求，一条路径经过所有的点，并且要求总代价最小

Solution

观察到 \(N\le 20\) 自然而然想到状压

因为多次经过一条边的代价是可以重复计算的，那么我们只需要考虑几个关键点就好了

比如说 \(1\Rightarrow 3\) 要经过 \(2\)，但是 \(2\) 不是关键节点，\(1\) 和 \(3\) 是

用 Floyd 计算出每两个节点之间的最短路

然后定义 \(F[S][k]\) 表示，在 \(S\) 的状态下，最后一时刻在 \(k\) 的最小代价

转移也很简单，枚举一个在 \(S\) 中的节点 \(j\)，把 \(j\) 从 \(S\) 中减去的集合称为 \(S-j\)

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1ll<<60;
int n,m,dp[1<<20][21];
int dist[21][21];
signed main(){
    for(int S=0;S<(1<<20);S++)
        for(int j=0;j<21;j++)
            dp[S][j] = INF;
    for(int i=0;i<21;i++)
        for(int j=0;j<21;j++)
            dist[i][j] = INF;
    cin>>n>>m;
    while(m--){
        int x,y; cin>>x>>y; x--; y--;
        int z; cin>>z; dist[x][y] = min(dist[x][y],z);
    }

    //Floyd
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);

    for(int i=0;i<n;i++)
        dp[1<<i][i] = 0; //初始化
    
    for(int S=1;S<(1<<n);S++)
        for(int j=0;j<n;j++)
            if((S>>j)&1)  //S 集合中有 j
                for(int k=0;k<n;k++)
                    if((S^(1<<j))>>k&1)  //S-j 集合中有 k
                        dp[S][j] = min(dp[S][j],dp[S^(1<<j)][k]+dist[k][j]);
    
    int ans = 1e9;
    for(int i=0;i<n;i++)
        ans = min(ans,dp[(1<<n)-1][i]);
    if(ans == 1e9) cout<<"No"<<endl;
    else cout<<ans<<endl;
    return 0;
}