This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// 巡回セールスマン問題 (重み付き有向グラフについて、次の条件を満たす最短経路の距離)
// ・ある頂点から出発して、出発点へ戻る閉路
// ・各頂点をちょうど 1 度通る
// -> 閉路なので、出発点はどこでもよい。この実装では 0 をスタートとしている。
// Verified: AOJ DPL_2_A: Traveling Salesman Problem
// (to, cost)
vector<pii> G[20];
int dp[1 << 15][15];
void solve() {
int V, E; cin >> V >> E;
rep(i,0,E) {
int s, t, d; cin >> s >> t >> d;
G[s].push_back(pii(t, d));
}
// 出発点だけ初期値 0 にする
rep(i,0,1<<V) rep(j,0,V) dp[i][j] = INF;
dp[0][0] = 0;
rep(bit,0,1<<V) rep(i,0,V) {
for(auto x : G[i]) {
if(bit >> x.first & 1) continue;
int nbit = bit | (1 << x.first);
chmin(dp[nbit][x.first], dp[bit][i] + x.second);
}
}
int ans = (dp[(1<<V)-1][0] == INF ? -1 : dp[(1<<V)-1][0]);
cout << ans << endl;
}
#line 1 "dp/dp_006_TSP.cpp"
// 巡回セールスマン問題 (重み付き有向グラフについて、次の条件を満たす最短経路の距離)
// ・ある頂点から出発して、出発点へ戻る閉路
// ・各頂点をちょうど 1 度通る
// -> 閉路なので、出発点はどこでもよい。この実装では 0 をスタートとしている。
// Verified: AOJ DPL_2_A: Traveling Salesman Problem
// (to, cost)
vector<pii> G[20];
int dp[1 << 15][15];
void solve() {
int V, E; cin >> V >> E;
rep(i,0,E) {
int s, t, d; cin >> s >> t >> d;
G[s].push_back(pii(t, d));
}
// 出発点だけ初期値 0 にする
rep(i,0,1<<V) rep(j,0,V) dp[i][j] = INF;
dp[0][0] = 0;
rep(bit,0,1<<V) rep(i,0,V) {
for(auto x : G[i]) {
if(bit >> x.first & 1) continue;
int nbit = bit | (1 << x.first);
chmin(dp[nbit][x.first], dp[bit][i] + x.second);
}
}
int ans = (dp[(1<<V)-1][0] == INF ? -1 : dp[(1<<V)-1][0]);
cout << ans << endl;
}