結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
![]() |
提出日時 | 2023-12-02 15:35:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 716 ms / 2,000 ms |
コード長 | 1,300 bytes |
コンパイル時間 | 473 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 169,728 KB |
最終ジャッジ日時 | 2024-09-26 18:58:36 |
合計ジャッジ時間 | 24,045 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
import collectionsimport heapqclass Dijkstra:def __init__(self):self.e = collections.defaultdict(list)def add(self, u, v, d):self.e[u].append([v, d])def delete(self, u, v):self.e[u] = [_ for _ in self.e[u] if _[0] != v]self.e[v] = [_ for _ in self.e[v] if _[0] != u]def search(self, s):""":param s: 始点:return: 始点から各点までの最短経路"""d = collections.defaultdict(lambda: 10**8)d[s] = 0q = []heapq.heappush(q, (0, s))v = collections.defaultdict(bool)while len(q):k, u = heapq.heappop(q)if v[u]:continuev[u] = Truefor uv, ud in self.e[u]:if v[uv]:continuevd = k + udif d[uv] > vd:d[uv] = vdheapq.heappush(q, (vd, uv))return dN,M = map(int, input().split())uv = [list(map(int, input().split())) for _ in range(M)]G = Dijkstra()RG = Dijkstra()for u,v in uv:G.add(u,v,1)D1 = G.search(1)DN = G.search(N)DN1 = G.search(N-1)ans = min(D1[N]+DN[N-1]+DN1[1],D1[N-1]+DN1[N]+DN[1])if ans<10**8:print(ans)else:print(-1)