結果

問題 No.2565 はじめてのおつかい
コンテスト
ユーザー Basin-Bug
提出日時 2023-12-02 16:18:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 404 ms / 2,000 ms
コード長 1,091 bytes
コンパイル時間 244 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 96,232 KB
最終ジャッジ日時 2024-09-26 20:07:39
合計ジャッジ時間 14,457 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

# 入力
N, M = map(int, input().split())
A, B = [ None ] * M, [ None ] * M
for i in range(M):
	A[i], B[i] = map(int, input().split())

# 隣接リストの作成 → グラフの辺を追加
G = [ list() for i in range(N + 1) ]
for i in range(M):
	G[A[i]].append((B[i], 1))

def dijkstra(beg):
  # ダイクストラ法：配列の初期化など
  dist = [ 10 ** 19 ] * (N + 1)
  used = [ False ] * (N + 1)
  Q = list()
  dist[beg] = 0
  heapq.heappush(Q, (0, beg))

  # ダイクストラ法：優先度付きキューの更新
  while len(Q) >= 1:
    pos = heapq.heappop(Q)[1]
    if used[pos] == True:
      continue
    used[pos] = True
    for i in G[pos]:
      to = i[0]
      cost = dist[pos] + i[1]
      if dist[to] > cost:
        dist[to] = cost
        heapq.heappush(Q, (dist[to], to))

  return dist

dist1 = dijkstra(1)
dist2 = dijkstra(N - 1)
dist3 = dijkstra(N)

if min(dist1[N - 1] + dist2[N] + dist3[1], dist1[N] + dist3[N - 1] + dist2[1]) < 10 ** 19:
  print(min(dist1[N - 1] + dist2[N] + dist3[1], dist1[N] + dist3[N - 1] + dist2[1]))
else:
  print(-1)
0