競プロ初中級者100問

JOI2016予選E ゾンビ島

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

ダイクストラ法
幅優先探索

はじめに

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

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

問題

https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_e

この問題は幅優先探索とダイクストラ法を用いて解くことができます。やや発展的な内容ですので、ダイクストラ法の練習のためにはまず下記の問題に取り組むことをオススメします。

JOI2008予選F 船旅

GRL1A Single Source Shortest Path

  • さらに簡単です。AOJ(Aizu Online Judge)というサイトの問題です。ダイクストラ法の基礎を学びたければこちらも良いでしょう。

方針

基本的には、解説の通りに実装すれば良いです。
この問題の解法は 2 つの段階からなる．1 つ目は危険な町を列挙する段階，2 つ目は宿泊費の合計が最小になる経路を見つける段階である．

  1. 危険な町を列挙
    • 幅優先探索
  2. 宿泊費の合計が最小になる経路を探索
    • ダイクストラ法

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from collections import deque
import heapq
INF = 10**20

N,M,K,S = map(int,input().split())
P,Q = map(int,input().split())

zombie = []
for k in range(K):
    zombie.append(int(input())-1)

link = [ [] for _ in range(N)]

for m in range(M):
    a, b = map(int, input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)

dist = [INF] * N
q = deque(zombie)
for v in zombie:
    dist[v] = 0
while q:
    node = q.popleft()
    for next in link[node]:
        if dist[next] != INF: # 探索済みの場合はパスされる。、
            continue          # distは小さい順にqに格納されるので、ゾンビからの最小距離を求めることがd系る
        dist[next] = dist[node] + 1
        q.append(next)

cost = [P] * N
for n in range(N):
    if dist[n] <= S:
        cost[n] = Q
    if n in zombie:
        cost[n] = INF
    if n==0 or n==N-1:
        cost[n] = 0

def dijkstra(s, g):
    dists  = [INF for i in range(N)]
    dists[s] = 0
    pq = [(0, s)] # 優先度付きキューのオブジェクトそのものはただのリスト
    while(pq[0][1]!=g):
        d, node = heapq.heappop(pq)
        if (d > dists[node]): # 探索の対象にする必要があるか確認
            continue
        for next in link[node]:
            c = cost[next]
            if d + c < dists[next]: # 探索の対象にする必要があるか確認
                dists[next] = d + c
                heapq.heappush(pq, (dists[next],next))
    return pq[0][0]
print (dijkstra(0,N-1))

記事情報

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