ABC 022 C

今回はこの問題です。

abc022.contest.atcoder.jp

頂点n個、辺m本からなる重みつきグラフが与えられます。頂点1を通る閉路(おなじ道を2回以上通らない)のうち、重みの和の最小値を求めましょうという問題です。

ダイクストラ法やワーシャルフロイド法ではおなじ道を2回以上通らないという条件を満たした解を得ることが難しいです。
そこで頂点1→(頂点1の隣接点)→(頂点1の隣接点)→頂点1の閉路を考えます。頂点1の隣接点ふたつの間の距離はワーシャルフロイド法で求めることができます。経路なのでおなじ道を2回以上通ることはありえません。したがって、頂点1の隣接点をa、bとすると(頂点aから頂点bの距離(ただし頂点1は通らない)) + (頂点1から頂点aの距離) + (頂点1から頂点bの距離)の最小値を求めればよいです。

回答は以下のようになります。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    void solve(int n, long long int r[301][301])
    {
        for(int k = 2; k <= n; k++){
            for(int i = 2; i <= n; i++){
                for(int j = 2; j <= n; j++){
                    r[i][j] = min(r[i][j], r[i][k] + r[k][j]);
                }
            }
        }
        return;
    }
     
    int main()
    {
        int n, m;
        cin >> n >> m;
        long long int road[301][301];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                road[i][j] = (long long int)mod * 1000;
            }
        }
        for(int i = 0; i < m; i++){
            int u, v, l;
            cin >> u >> v >> l;
            road[u][v] = l;
            if(u != 1) road[v][u] = l;
        }
        long long int ans = (long long int)mod * 1000;
        solve(n, road);
        for(int i = 2; i <= n; i++){
            if(road[1][i] == 0) continue;
            for(int j = i + 1; j <= n; j++){
                if(road[1][j] == 0) continue;
                ans = min(ans, road[1][i] + road[i][j] + road[1][j]);
            }
        }
        if(ans == (long long int)mod * 1000) cout << -1 << endl;
        else cout << ans << endl;
        return 0;
    }

ansとかroadの初期値をmod * 1000にしているのはmod以上の解がありそうだと思ったからです。
uが1のときはroad[v][u]の値を変更しないようにしているのは、vから1への道はないものとすることで1を通らない経路を見つけるためです。これは一回ダイクストラ法を使おうとしたときの名残です。それぞれの頂点に対してダイクストラ法を実行しようと思ったらTLEしたので、ワーシャルフロイド法を使うことにしました。ワーシャルフロイド法ならこんなことをしなくても大丈夫です。