結果
問題 |
No.1995 CHIKA Road
|
ユーザー |
|
提出日時 | 2024-04-16 11:29:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,037 ms / 2,000 ms |
コード長 | 1,034 bytes |
コンパイル時間 | 387 ms |
コンパイル使用メモリ | 82,204 KB |
実行使用メモリ | 195,508 KB |
最終ジャッジ日時 | 2024-10-07 05:17:37 |
合計ジャッジ時間 | 16,553 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
from collections import defaultdict from heapq import heappop, heappush from itertools import pairwise from math import inf def main(): N, M = map(int, input().split()) graph = defaultdict(dict) roads_edge = set((0, N - 1)) for _ in range(M): A, B = map(int, input().split()) roads_edge.add(A - 1) roads_edge.add(B - 1) graph[A - 1][B - 1] = 2 * (B - A) - 1 roads_edge = sorted(roads_edge) for prev_n, cur_n in pairwise(roads_edge): graph[prev_n][cur_n] = min( 2 * (cur_n - prev_n), graph[prev_n].get(cur_n, inf)) distance = {edge: inf for edge in roads_edge} distance[0] = 0 queue = [(0, 0)] while queue: c_d, c_n = heappop(queue) if distance[c_n] < c_d: continue for n_n, n_d in graph[c_n].items(): if distance[n_n] > n_d + c_d: distance[n_n] = n_d + c_d heappush(queue, (n_d + c_d, n_n)) print(distance[N - 1]) if __name__ == "__main__": main()