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