【ABC191】 E - Come Back Quickly

atcoder.jp

水diffになってるけど、適切な位置に出題されていれば茶〜緑ぐらいの難易度だと思った。

考察

dist[i] ← 始点からiまでの最短距離
n.w ← 辺の重み
とする。
各頂点を始点としてダイクストラをして、頂点iから元の頂点へ戻る辺を通る時にdist[i] + n.wの最小値を取ればよい。
queueから頂点が取り出された時点でその頂点への最短距離はすでに求まっているので、これで正しい答えを得ることができる。

別解

ダイクストラをやるのは同じでも、全頂点対についての最短距離を先に求めておく方法でも解ける。
dist[i→j] ← 頂点iからjまでの最短距離
とし、頂点iから頂点iへ繋がっている辺を通らないとすると、 頂点iを出て頂点iに戻ってくる最短距離は、 dist[i→j] + dist[j→i] が最小になるような頂点jを全探索することで求められる。

公式解説 atcoder.jp

実装

一つ目の解法の実装を載せている。

struct Edge {
    long long to; // 隣接頂点番号
    long long w; // 重み
    Edge(long long to, long long w) : to(to), w(w) {}
};

using Graph = vector<vector<Edge>>;

int main(){
    ll N, M;
    cin >> N >> M;
    vector<ll> A(M), B(M), C(M);
    REP (i, M) cin >> A[i] >> B[i] >> C[i];

    Graph G(N);
    REP (i, M) G[A[i]-1].push_back({B[i]-1, C[i]});

    REP (i, N) {
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> que;
        vector<ll> dist(N, INF64);
        que.push({0, i});
        dist[i] = 0;
        ll ans = INF64;

        while (!que.empty()) {
            ll d = que.top().first;
            ll p = que.top().second;
            que.pop();

            if (d > dist[p]) continue;

            for (auto n : G[p]) {
                if (i == n.to) chmin(ans, dist[p] + n.w);

                if (chmin(dist[n.to], dist[p] + n.w)) {
                    que.push({dist[n.to], n.to});
                }
            }
        }

        c((ans == INF64 ? -1 : ans))
    }
    
    return 0;
}