結果
問題 | No.1995 CHIKA Road |
ユーザー |
![]() |
提出日時 | 2022-07-01 21:46:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 347 ms / 2,000 ms |
コード長 | 781 bytes |
コンパイル時間 | 419 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 134,476 KB |
最終ジャッジ日時 | 2024-11-26 04:37:35 |
合計ジャッジ時間 | 8,060 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
""" """ from sys import stdin N,M = map(int,stdin.readline().split()) town = set() town.add(1) town.add(N) lis = edge = {} for i in range(M): A,B = map(int,stdin.readline().split()) town.add(A) town.add(B) if A not in edge: edge[A] = [] edge[A].append(B) ans = {} tl = list(town) tl.sort() for i in range(len(tl)): v = tl[i] if i == 0: ans[v] = 0 else: lastv = tl[i-1] if v not in ans: ans[v] = float("inf") ans[v] = min(ans[v] , ans[lastv] + 2 * (v-lastv)) if v in lis: for nex in lis[v]: if nex not in ans: ans[nex] = float("inf") ans[nex] = min(ans[nex] , ans[v] + 2*(nex-v)-1) print (ans[N])