競技プログラミングを最近はじめたPython初学者です。第15回日本情報オリンピック予選 E問題のゾンビ島について質問があります。
私のコードはサンプルでは正しい出力をしており、自分で考えた入力に対しても正しい出力が出ています。しかし、提出した結果、不正解(WA)となってしまいます。デバッグし1行ずつ確認してみたり、色々と調べてみたりしたのですが、原因が全くわかません。原因がわかる方がいらっしゃいましたら、教えていただけると幸いです。何卒よろしくお願いいたします。
ゾンビ島
問題は以下のリンクです
[リンク] https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_e
コード
python
1import sys 2import heapq 3from collections import deque 4# 入力処理高速化 5def input(): return sys.stdin.readline().rstrip() 6 7 8# 入力受付 9N, M, K, S = map(int, input().split()) 10P, Q = map(int, input().split()) 11C = [int(input()) for _ in range(K)] 12 13# グラフ作成 14graph = [[] for _ in range(N+1)] 15for _ in range(M): 16 a, b = map(int, input().split()) 17 graph[a].append(b) 18 graph[b].append(a) 19 20# ゾンビがいる島はTrue 21zonbieIsland = [False]*(N+1) 22for c in C: 23 zonbieIsland[c] = True 24 25# 宿泊料を決める 26# はじめは危険じゃない島人して考えてP円とする 27accomFee = [P]*(N+1) 28# ゾンビがいる島の数だけループ 29for c in C: 30 # 距離とキューの初期化 31 dist = [-1] * (N+1) 32 dist[c] = 0 33 d = deque([c]) 34 35 # 幅優先探査(BFS)で危険な島を見つける 36 while d: # dに一つでも要素が入っているときは処理を続ける 37 v = d.popleft() 38 for i in graph[v]: 39 if dist[i] != -1: 40 continue 41 if dist[v] + 1 <= S: 42 dist[i] = dist[v]+1 43 d.append(i) 44 45 for i in range(1, N+1): 46 # 危険な島だったら料金をQ円に更新 47 if dist[i] != -1: 48 accomFee[i] = Q 49 50# N番目の島は宿泊料を考えないため0円 51accomFee[N] = 0 52 53# ダイクストラ法 54INF = float('INF') 55 56fee = [INF]*(N+1) 57fee[1] = 0 58visited = [False]*(N+1) 59h = [(0, 1)] 60 61while h: 62 f, v1 = heapq.heappop(h) # その町までの料金, 頂点 (最小料金のものから優先的に選ぶ) 63 if visited[v1]: 64 continue 65 visited[v1] = True 66 # 町v1からつながるすべての町へのコストを確認 67 for v2 in graph[v1]: 68 # ゾンビ島だったら訪れない 69 if v2 not in zonbieIsland: 70 # 料金の更新 71 if fee[v2] > fee[v1] + accomFee[v2]: 72 fee[v2] = fee[v1] + accomFee[v2] 73 heapq.heappush(h, (accomFee[v2], v2)) 74 75print(fee[N]) 76

回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2022/01/17 11:32
2022/01/17 13:27 編集