競プロ初中級者100問

ABC074D Restoring Road Network

この記事で使うアルゴリズム

ワーシャルフロイド法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc074/tasks/arc083_b

この問題を解く前に、ワーシャルフロイド法を用いた最短経路問題の解き方について理解しておくことをお勧めします。

解説

2つの問題を同時に解いていきます

  1. 都市uから都市vへの最短経路の長さとなるような道路の構造が存在するか
  2. 存在する道路の長さの和が最小となるようなものについて、その和

都市uから都市vへの最短経路の長さとなるような道路の構造が存在するか

都市uから都市vへ移動する間にどの別の1つの都市を通っても、表に記された値より小さいコストで移動できないことを確認すれば良いです。

存在する道路の長さの和が最小となるようなものについて、その和

2つ目の問題は、都市uから都市vへ移動する間にどの別の1つの都市を通っても、表に記された値と等しいコストで移動できない場合、直接結ぶ道路が必要ということになります。そのようなコストを足し合わせていけば良いです。

ポイント

  • u < vとする
    • 道路は双方向に結ばれているので、二重にカウントしてはならない
    • u != vとした方が、条件分岐の実装が楽になる
  • cost[u][u] = INFとする
    • cost[u][u]=0としてしまうと、u->u->vとu->vの値が常に等しくなる。これを避けた方が条件分岐の実装が楽になる

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
N = int(input())
INF = 10**10
cost = [[INF]*N for _ in range(N)] # INFで初期化v

for u in range(N):
    C = list(map(int, input().split()))
    for v in range(N):
        if u==v: # 自身への道路はINFのままにする
            continue
        cost[u][v] = C[v]
 
ans = 0
for u in range(N):
    for v in range(u+1,N): # u < v
        mn = INF # u-w-vのような経路の中で最小の距離を求める
        for w in range(N):
            mn = min(mn, cost[u][w]+cost[w][v])    
        if (cost[u][v] > mn): # 与えられた行列が最短経路ではない
            print (-1) # 終了して良い
            exit()
        elif (cost[u][v] < mn): # 等しくない場合はu-vを直接結ぶ道路が必要 
            ans += cost[u][v]                      
print (ans)

記事情報

  • 投稿日：2020年4月22日
  • 最終更新日：2020年5月8日