AtCoder ABC 073 D - joisino's travel (水色, 400 点)

Floyd-Warshall で前処理してどうのこうのする問題。特に ICPC 系などでよくある！

問題へのリンク

問題概要

頂点 辺の重み付き無向グラフが与えられる。

このグラフ上で 個のチェックポイントをなす頂点集合が指定されている。好きなチェックポイントからスタートして好きなチェックポイントで終えて良い。すべてのチェックポイントへアクセスするのに必要な最小移動距離を求めよ。

制約

• 
• 

考えたこと

通りの探索順を試す TSP の一種な感じ。ここで

• チェックポイント a からチェックポイント b への最短移動距離

を各 (a, b) ペアについて求めておきたくなる。それについては予め Floyd-Warshall 法を用いて全頂点対について最短路長を前処理して求めておくのがよさそう。

そして 通りの探索については、C++ では std::next_permutation を用いるのが便利。もう少し制約が大きくて とかだったら 通りの全探索は間に合わないので bitDP などを検討することになる。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1LL<<60;
const int MAX = 210;

int N, M, R;
long long dist[MAX][MAX];

int main() {
    cin >> N >> M >> R;
    vector<int> vr;
    for (int i = 0; i < R; ++i) {  int r; cin >> r; --r; vr.push_back(r); }
    
    // Floyd-Warshall の初期化: dist[i][i] = 0 に注意
    for (int i = 0; i < 210; ++i) {
        for (int j = 0; j < 210; ++j) dist[i][j] = INF;
        dist[i][i] = 0;
    }
    
    // 入力と Floyd-Warshall
    for (int i = 0; i < M; ++i) {
        int a, b, c; cin >> a >> b >> c; --a, --b;
        dist[a][b] = c;
        dist[b][a] = c;
    }
    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]);

    // R! 通りの探索
    long long res = INF;
    sort(vr.begin(), vr.end());
    do {
        long long tmp = 0;
        for (int i = 1; i < vr.size(); ++i) tmp += dist[vr[i]][vr[i-1]];
        res = min(res, tmp);
    } while (next_permutation(vr.begin(), vr.end()));

    cout << res << endl;
}