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); } }