競プロ初中級者100問

ABC079D Wall

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

ワーシャルフロイド法

はじめに

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

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

問題

https://atcoder.jp/contests/abc079/tasks/abc079_d

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

解説

ある数字を1に変えるために他の数字を経由することで、直接書き換えるよりコストを節約できるケースがあります。

つまり、この問題は魔力をコストとした最短経路問題と言えます。

一旦、最短経路を求めてしまえば、あとは壁に書かれている数字に対し1への変換コストを求めて足していけば良いです。

解法としては

  • ダイクストラ法をN回適用する
  • ワーシャルフロイド法
    などが考えられます。どちらも計算量はO(N^3)です。

今回の問題は隣接行列が対称行列となっていない点に注意が必要ですが、これらのアルゴリズムは問題なく適用できます。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
H, W = map(int, input().split())
INF = 10**10
N = 10
cost = [[INF]*N for _ in range(N)] # 隣接行列

for i in range(N):
    C = list(map(int, input().split()))
    for j in range(N):
        cost[i][j] = C[j]

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]) 

ans = 0 # 和
for h in range(H):
    A = list(map(int, input().split()))
    for a in A:
        if a!=-1: # -1出なければ足す
            ans += cost[a][1] # 対称行列ではないので注意する

print (ans)

記事情報

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