https://beta.atcoder.jp/contests/abc073/tasks/abc073_d
前提知識
- ワーシャルフロイド
解法
https://beta.atcoder.jp/contests/abc073/submissions/1578676
今回重要な条件があり「2≦R≦min(8,N)」である。
つまり、配列rの全ての組み合わせを試すことができる。
c++であればnext_permutation関数で全ての順列を試せる。
あとは、二点間の最短距離を高速に求められばいいが、ワーシャルフロイドという手法を使う。
これを使えばO(N^3)で二点間の最短距離が求められるので、事前に計算しておく。
int N, M, R; int d[202][202]; int r[202]; #define INF INT_MAX/2 //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M >> R; rep(i, 0, R) cin >> r[i]; rep(i, 0, N) rep(j, 0, N) { if (i == j) d[i][j] = 0; else d[i][j] = INF; } rep(i, 0, M) { int a, b, c; cin >> a >> b >> c; a--; b--; d[a][b] = c; d[b][a] = c; } rep(k, 0, N) rep(i, 0, N) rep(j, 0, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); vector<int> v; rep(i, 0, R) v.push_back(r[i] - 1); sort(v.begin(), v.end()); int ans = INF; do { int sm = 0; rep(i, 0, R - 1) sm += d[v[i]][v[i + 1]]; ans = min(ans, sm); } while (next_permutation(v.begin(), v.end())); cout << ans << endl; }