競技プログラミングを最近はじめたPython初学者です。第15回日本情報オリンピック予選 E問題のゾンビ島について質問があります。
私のコードはサンプルでは正しい出力をしており、自分で考えた入力に対しても正しい出力が出ています。しかし、提出した結果、不正解(WA)となってしまいます。デバッグし1行ずつ確認してみたり、色々と調べてみたりしたのですが、原因が全くわかません。原因がわかる方がいらっしゃいましたら、教えていただけると幸いです。何卒よろしくお願いいたします。
ゾンビ島
問題は以下のリンクです
[リンク] https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_e
コード
python
import sys import heapq from collections import deque # 入力処理高速化 def input(): return sys.stdin.readline().rstrip() # 入力受付 N, M, K, S = map(int, input().split()) P, Q = map(int, input().split()) C = [int(input()) for _ in range(K)] # グラフ作成 graph = [[] for _ in range(N+1)] for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) # ゾンビがいる島はTrue zonbieIsland = [False]*(N+1) for c in C: zonbieIsland[c] = True # 宿泊料を決める # はじめは危険じゃない島人して考えてP円とする accomFee = [P]*(N+1) # ゾンビがいる島の数だけループ for c in C: # 距離とキューの初期化 dist = [-1] * (N+1) dist[c] = 0 d = deque([c]) # 幅優先探査(BFS)で危険な島を見つける while d: # dに一つでも要素が入っているときは処理を続ける v = d.popleft() for i in graph[v]: if dist[i] != -1: continue if dist[v] + 1 <= S: dist[i] = dist[v]+1 d.append(i) for i in range(1, N+1): # 危険な島だったら料金をQ円に更新 if dist[i] != -1: accomFee[i] = Q # N番目の島は宿泊料を考えないため0円 accomFee[N] = 0 # ダイクストラ法 INF = float('INF') fee = [INF]*(N+1) fee[1] = 0 visited = [False]*(N+1) h = [(0, 1)] while h: f, v1 = heapq.heappop(h) # その町までの料金, 頂点 (最小料金のものから優先的に選ぶ) if visited[v1]: continue visited[v1] = True # 町v1からつながるすべての町へのコストを確認 for v2 in graph[v1]: # ゾンビ島だったら訪れない if v2 not in zonbieIsland: # 料金の更新 if fee[v2] > fee[v1] + accomFee[v2]: fee[v2] = fee[v1] + accomFee[v2] heapq.heappush(h, (accomFee[v2], v2)) print(fee[N])
まだ回答がついていません
会員登録して回答してみよう