ゆらのふなびと

競プロ, Python, C++

ABC022 C - Blue Bird

想定解と違うっぽかったので書いておきます。(ダイクストラで解いた)

問題

abc022.contest.atcoder.jp

グラフが与えられるので、地点1から出発し地点1に戻ってくるような閉路が存在するとき、その最小の重みの和を求めよ。そのような閉路が存在しないときは-1を出力せよ。

制約

街の個数:  3 \leq N \leq 300

道の本数:  3 \leq M \leq N (N - 1) / 2

各辺の重み:  1 \leq l_i \leq 10^5

解法

まず、公式の解法は以下の通りです。

  1. 頂点1から出る辺をすべて除去したグラフでワーシャルフロイド O(N^3)
  2. 頂点1に接続する頂点から2つu, vを選んで、1->u + u ->v + v ->1 の最小値を求める O(N^2)

仮にこの解法で最短経路を求めるのにダイクストラを使ったとしましょう。すると2で列挙する(u, v)の組に対し最短経路の計算を毎回することになるので O(N^4)となり間に合いません。そのため全点最短路対を一気に求められるワーシャルフロイドを用いるのでした。

しかし、以下の考え方ならダイクストラでも解けます。

  1. 頂点1から出る辺のうち1つを除去する。この辺の頂点1でない端点をuとする。 O(N)
  2. 1で得られたグラフに対し頂点1からダイクストラを行い、1->u + u->1(削除した辺の重み)の最小値をuについて求める O(N^2)

上の解法は、頂点1に戻ってくる直前の頂点がuならば、必ず閉路にu->1が含まれることを利用しています。また、万一頂点uが最終直前の頂点となるような閉路が存在しない場合は、1->uの辺を削除したグラフでダイクストラすると1->uの最短距離がINFとなるのでこれが採用されることはありません。

辺を削除・復元するのが隣接リストだとやりにくかったので、隣接行列を用いました。1のループの中に毎回2が入っているので、計算量は公式の解法と同じく O(N^3)です。

const int INF = 99999999;
const int MAX_V = 1000;
const int MAX_E = 100000;
 
int cost[MAX_V][MAX_V];
int d[MAX_V];
bool used[MAX_V];
//int pre[MAX_V];
int V, E;
 
void init_cost() {
    REP(i, V) REP(j, V) cost[i][j] = INF;
}
 
void input() {
    scanf("%d%d", &V, &E);
 
    init_cost();
    REP(i, E) {
        int f, t, c;
        scanf("%d%d%d", &f, &t, &c);
        f--; t--;
        cost[f][t] = c;
        cost[t][f] = c;
    }
}
 
//s: start
void dijkstra(int s) {
    REP(i, V) d[i] = INF;
    REP(i, V) used[i] = false;
    //REP(i, V) pre[i] = -1;
    d[s] = 0;
 
    while (true) {
        int v = -1;
        REP(u, V) if (!used[u] && (v == -1 | d[u] < d[v])) v = u;
 
        if (v == -1) break;
        used[v] = true;
 
        REP(u, V) {
            if (d[u] > d[v] + cost[v][u]) {
                d[u] = d[v] + cost[v][u];
                //pre[u] = v;
            }
        }
    }
}
 
void solve() {
    int ans = INF;
    REP(i, V) {
        if (cost[0][i] == INF) continue;
 
        //0からiへの道があれば、一度削除してダイクストラ
        int t_c = cost[0][i];
        cost[0][i] = cost[i][0] = INF;
        dijkstra(0);
 
        ans = min(ans, d[i] + t_c);
 
        //辺を復元
        cost[0][i] = cost[i][0] = t_c;
    }
 
    if (ans == INF) {
        ans = -1;
    }
    printf("%d\n", ans);
}
 
int main() {
    input();
    solve();
    return 0;
}

ABCのC問題あと8問。