競プロ初中級者100問

GRL1C 全点対間最短経路

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

ワーシャルフロイド法

はじめに

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

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

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=ja

この問題はワーシャルフロイド法を用いて解くことができます。

解説

このような問題は最短経路問題の中でも全点対最短経路問題と言います。

解法としては

  • ダイクストラ法をN回適用する
  • ワーシャルフロイド法
    などが考えられます。

ただし、負の重みがある場合はダイクストラ法を適用することはできません。そのため、今回はワーシャルフロイド法を用います。負の閉路がある場合、ワーシャルフロイド法の計算の結果、自身への最短距離dist[n][n]が負の値となります。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
N, M = map(int, input().split())
INF = float('inf')
cost = [[INF]*N for _ in range(N)]
for n in range(N):
    cost[n][n] = 0
for m in range(M):
    a, b, t = map(int, input().split())
    cost[a][b] = t

for i in range(N): # 中継点
    for j in range(N): # 始点
        for k in range(N): # 終点
            cost[j][k] = min(cost[j][i]+cost[i][k], cost[j][k])

for n in range(N):
    if cost[n][n] < 0:
        print ('NEGATIVE CYCLE')
        exit()

for c in cost:
    c = [str(i).replace('inf','INF') for i in c]
    print(' '.join(c))

記事情報

  • 投稿日：2020年5月31日
  • 最終更新日：2020年5月31日