はまやんはまやんはまやん

hamayanhamayan's blog

joisino's travel [AtCoder Beginner Contest 073 D]

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;
}