結果
問題 | 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<<60v=[X]*lv[0]=0q=[(v[0],0)]from heapq import heappush,heappopwhile len(q)>0:sc,sp=heappop(q)if sc>v[sp]:continuefor tp,tc in e[sp]:if v[tp]>sc+tc:v[tp]=sc+tcheappush(q,(v[tp],tp))print(v[-1])