はまやんはまやんはまやん

hamayanhamayan's blog

Min Distances [CSAcademy #70 C]

https://csacademy.com/contest/round-70/task/min-distances/

以下の条件を満たすN頂点の重み付き無向グラフを構築せよ。

  • M本の「頂点aと頂点bの最短距離がc」という情報をすべて満たす
  • 無向グラフはシンプルで連結である

前提知識

  • ワーシャルフロイド
  • UnionFind

解法

まずは、与えられるM本の辺を使って無向グラフをとりあえず作ろう。
次に、そのグラフ上でワーシャルフロイドを行い、各頂点の最短距離を求めておく。
そして、与えられるM本の辺とワーシャルフロイドの結果を照合して正しいかを確かめよう。
もし、矛盾するなら-1である。
 
概ねこれでいいが、無向グラフは連結である必要がある。
そのため、連結出ない場合は、辺の重みを∞として辺を張って無理矢理連結にする。
∞は10^7を使えばいい。
連結かどうかのチェックにはUnionFindを使用した。
連結成分が2個以上ある場合は、各連結成分の代表の点を∞の辺で繋げて連結にして答える。

using tiii = tuple<int, int, int>;
int N, M, A[10101], B[10101], C[10101];
int d[101][101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) rep(j, 0, N) {
        if (i == j) d[i][j] = 0;
        else d[i][j] = inf;
    }
    rep(i, 0, M) {
        cin >> A[i] >> B[i] >> C[i];
        A[i]--; B[i]--;
        d[A[i]][B[i]] = d[B[i]][A[i]] = C[i];
    }
    rep(k, 0, N) rep(i, 0, N) rep(j, 0, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    rep(i, 0, M) if (d[A[i]][B[i]] < C[i]) {
        printf("-1\n");
        return;
    }
    
    vector<tiii> ans;
    UnionFind uf(N);
    rep(i, 0, N) rep(j, i+1, N) if(d[i][j] <= 10000000) {
        ans.push_back(make_tuple(i, j, d[i][j]));
        uf(i, j);
    }

    vector<int> g;
    rep(i, 0, N) if (uf[i] == i) g.push_back(i);

    rep(i, 1, g.size()) {
        ans.push_back(make_tuple(g[0], g[i], 10000000));
    }

    int n = ans.size();
    printf("%d\n", n);
    fore(t, ans) {
        int a, b, c;
        tie(a, b, c) = t;
        printf("%d %d %d\n", a + 1, b + 1, c);
    }
}