ABC 022 C - Blue Bird

問題

問題概要

省略

解法

ダイクストラでやろうと思うと、閉路の最短距離を出すのは普通にやったらできない。求めるのは0から初めて、0に戻るような閉路で最短距離。そのような経路は、0 -> u -> v -> 0 ものである。同じ道を２度通ることはできないので、uとvは異なる。
実装方法は、0に隣接する異なる２点をuとvとする。そして、u、vの最短距離はワーシャルフロイドで求めておけばいい。ただし、このとき注意しなければならないのは、与えられたグラフのままそのままワーシャルフロイドを行うと、u->vの最短距離が、u -> 0 -> v　の経路で求まったものになる可能性がある。よって、ワーシャルフロイドをする前に、0に隣接する辺をすべて除き、ワーシャルフロイドを行うことで、正確におこなうことができる。
答えは、(0 - u　の距離) + (u - v　の最短距離) + (v - 0　の距離)　となる。 公式解説がわかりやすい

AtCoder Beginner Contest 022 解説 from AtCoder Inc.

www.slideshare.net

ミス

普通にわからなかった。dfsで何かやるのかと思った。 勉強になった。

コード

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int n, m;
int d[310][310];

void warshall_floyd(){
    for (int k = 0; k < n; ++k){
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < n; ++j){
                d[i][j] = min(d[i][j], d[i][k] + d[j][k]);
            }
        }
    }
}

int main(void){
    cin >> n >> m;
    rep(i, 310)rep(j, 310) d[i][j] = INF;
    rep(i, 310) d[i][i] = 0;
    vector<pair<int, int> > tonari;//0 -> u (0に隣接している頂点)

    rep(i, m){
        int tu, tv, tl;
        cin >> tu >> tv >> tl; tu--; tv--;
        if(tu == 0){
            tonari.push_back(make_pair(tv, tl));
            continue;
        }else if(tv == 0){
            tonari.push_back(make_pair(tu, tl));
            continue;
        }
        //0に隣接する辺でなければ、グラフに追加する
        //0に隣接する辺まで入れてしまうと、u-vの最短経路を求めるときに、
        // 頂点0を通る最短経路を考えてしまう可能性がある
        d[tu][tv] = d[tv][tu] = tl;
    }
    warshall_floyd();
    int ans = INF;
    for(auto u : tonari){
        for(auto v : tonari){
            if(u.first == v.first) continue;
            //0 - u - v - 0の閉路の距離(u - vの間で0を通らない)
            int l = u.second + d[u.first][v.first] + v.second;
            ans = min(ans, l);
        }
    }
    if(ans == INF) printf("-1\n");
    else printf("%d\n", ans);
    return 0;
}