質問をすることでしか得られない、回答やアドバイスがある。

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

新規登録して質問してみよう
ただいま回答率
87.20%
Python 3.x

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

解決済

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

OOO4423
OOO4423

総合スコア8

Python 3.x

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

1回答

0評価

0クリップ

262閲覧

投稿2022/01/17 06:17

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

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

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

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

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

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

まだ回答がついていません

会員登録して回答してみよう

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

ただいまの回答率
87.20%

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

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

質問する

関連した質問

同じタグがついた質問を見る

Python 3.x

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