mayoko’s diary

プロコンとかいろいろ。

ABC #022 C - Blue Bird

ABC #022に参加。途中で抜けたとはいえABしか解けなかったのはひどい。

問題:C: Blue Bird - AtCoder Beginner Contest 022 | AtCoder

解法:0から出発して0に帰ってくるような閉路は,
0->a->...->b->0
というように0からaに出て行って何かを経由してからbに来てそこから0に戻る,というように記述することができる。この「...」のところで0を通らなければ閉路になるので,「a->...->b」の部分は「0を通らないという条件のもとでのaとbの最短経路」が求まれば良いことになる。これはワーシャルフロイドで実行することが可能。下のソースコード,distとdist2があるけどよく考えたらdistはいらない気がしてきた。
以下ソースコード

int N, M;
const int MAXN = 333;

const ll INF = 1LL<<55;
ll dist[MAXN][MAXN];
ll dist2[MAXN][MAXN];
ll adj[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        dist[i][j] = INF;
        dist2[i][j] = INF;
    }
    for (int i = 0; i < N; i++) {
        dist[i][i] = 0;
        dist2[i][i] = 0;
        adj[i] = INF;
    }
    adj[0] = 0;
    for (int i = 0; i < M; i++) {
        int u, v, l;
        cin >> u >> v >> l;
        u--;
        v--;
        dist[u][v] = dist[v][u] = l;
        if (u != 0 && v != 0) dist2[u][v] = dist2[v][u] = l;
        else {
            adj[v] = l;
        }
    }
    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]);
            }
        }
    }
    for (int k = 1; k < N; k++) {
        for (int i = 1; i < N; i++) {
            for (int j = 1 ;j < N; j++) {
                dist2[i][j] = min(dist2[i][j], dist2[i][k] + dist2[k][j]);
            }
        }
    }
    ll ans = INF;
    for (int i = 1; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            ans = min(ans, adj[i] + dist2[i][j] + adj[j]);
        }
    }
    if (ans >= INF) ans = -1;
    cout << ans << endl;
    return 0;
}