ABC022 C問題 Blue Bird

頂点1からその頂点にもどるとき、同じ道を使わない最短経路の最小コストを出力する問題。

ダイクストラとかを変形して使えないかなぁと考えたけど無理。
なんとかして最短経路問題に落ち着かせられないか。

頂点0に直接つながっている頂点を2つ選んで、その2つの頂点の最短経路問題に落ち着かせればよい。
頂点を2つ選ぶのにO(N^2)
最短経路問題でワーシャルフロイドならO(N^3)で全てを済ませられる。

この考え方はなかったので面白い。

const int INF = 1e9;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, M; cin >> N >> M;
    int G[N][N];
    rep(i, N) rep(j, N) G[i][j] = INF;
    vector<P> T;
    for(int i=0; i<M; i++){
        int u, v, l; cin >> u >> v >> l; u--; v--;
        G[u][v] = l;
        G[v][u] = l;
        if(u == 0) T.push_back(P(v, l));
        if(v == 0) T.push_back(P(u, l));
    }

    for(int i=0; i<len(T); i++){
        G[0][T[i].first] = INF;
        G[T[i].first][0] = INF;
    }
    for(int k=0; k<N; k++){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
            }
        }
    }
    int res = -1;
    for(int i=0; i<len(T); i++){
        for(int j=i+1; j<len(T); j++){
            int d = T[i].second + T[j].second + G[T[i].first][T[j].first];
            if(d < INF && (res == -1 || d < res)){
                res = d;
            }
        }
    }
    cout << res << endl;
}