ABC338 F. Negative Traveling Salesman
Difficulty:1835
問題文
#ABC338 #ABC
#bitDP #ワーシャルフロイド法
問題
N頂点M辺の重み付き単純無向グラフがある。負閉路は存在しない。
N頂点を通るウォークが存在するか判定し、存在する場合は重みの操作の最小値を求めよ。
解法
ワーシャルフロイド法で全頂点対最短距離を前計算しておき、素直にbitDPをすればよい。
dp[S][i] = これまでに訪れた頂点集合がSで、最後にいる頂点番号がiであるときの重みの最小値
実装
提出コード
code:cpp
bool solve(){
LL(n,m);
vector<vector<pair<ll,ll>>>g(n);
vector dist(n,vector(n,INF));
rep(i,m){
LL(u,v,w);
u--,v--;
gu.push_back({v,w});
chmin(distuv,w);
}
rep(i,n)distii = 0;
rep(k,n){
rep(i,n){
rep(j,n){
chmin(distij,distik+distkj);
}
}
}
vector dp(1<<n,vector(n,INF));
rep(i,n)dp(1<<i)i = 0;
rep(i,1<<n){
rep(j,n){
if(dpij==INF)continue;
rep(k,n){
if(distjk==INF)continue;
chmin(dpi|(1<<k)k,dpij+distjk);
}
}
}
ll ans{INF};
rep(i,n){
chmin(ans,dp(1<<n)-1i);
}
if(ans==INF)O("No");
else O(ans);
return false;
}