teratail header banner
teratail header banner
質問するログイン新規登録
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

1回答

796閲覧

Python JOI:「ゾンビ島」 の解法について (ダイクストラ法, 幅優先探査(BFS)), Atcoder

OOO4423

総合スコア18

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

0グッド

0クリップ

投稿2022/01/17 06:17

0

0

 競技プログラミングを最近はじめた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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

Python

1 heapq.heappush(h, (accomFee[v2], v2))

ここが(その町までの料金, 頂点)になってません。


# ゾンビ島だったら訪れない if v2 not in zonbieIsland:

ここもコメントとコードが一致してないですね。

投稿2022/01/17 08:33

編集2022/01/17 11:48
yudedako67

総合スコア2052

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

OOO4423

2022/01/17 11:32

ご指摘ありがとうございます。 なるほど。正しくは、 heapq.heappush(h,(fee[v2],v2)) でしょうか。しかし、これでも正解にはなりませんが、他に原因などわかりますか?
OOO4423

2022/01/17 13:27 編集

ご指摘ありがとうございます if not zonbieIslad[v2]: に修正すればACしました。こんな基本的なことに気づかないとは恥ずかしいです。 また機会があればその時は何卒よろしくおねがいします。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.30%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問