結果
問題 |
No.1995 CHIKA Road
|
ユーザー |
![]() |
提出日時 | 2024-08-25 21:07:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 731 ms / 2,000 ms |
コード長 | 534 bytes |
コンパイル時間 | 411 ms |
コンパイル使用メモリ | 82,088 KB |
実行使用メモリ | 168,572 KB |
最終ジャッジ日時 | 2024-08-25 21:08:05 |
合計ジャッジ時間 | 14,145 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
n,m=map(int,input().split()) z=[1,n] es=[] for i in range(m): a,b=map(int,input().split()) es+=[(a,b)] z+=[a,b] z=sorted(set(z)) d={v:i for i,v in enumerate(z)} l=len(z) e=[[] for i in range(l)] for i in range(l-1): e[i]+=[(i+1,(z[i+1]-z[i])*2)] for a,b in es: e[d[a]]+=[(d[b],2*b-2*a-1)] X=1<<60 v=[X]*l v[0]=0 q=[(v[0],0)] from heapq import heappush,heappop while len(q)>0: sc,sp=heappop(q) if sc>v[sp]: continue for tp,tc in e[sp]: if v[tp]>sc+tc: v[tp]=sc+tc heappush(q,(v[tp],tp)) print(v[-1])