結果
問題 | No.1812 Uribo Road |
ユーザー |
![]() |
提出日時 | 2024-11-22 11:42:01 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 585 bytes |
コンパイル時間 | 338 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 1,116,240 KB |
最終ジャッジ日時 | 2024-11-22 11:43:13 |
合計ジャッジ時間 | 70,335 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 TLE * 9 MLE * 5 |
ソースコード
n,m,k=map(int,input().split()) r=[-1]*m for i,v in enumerate(list(map(int,input().split()))): r[v-1]=i e=[[] for i in range(n)] for i in range(m): a,b,c=map(int,input().split()) a-=1 b-=1 e[a]+=[(i,b,c)] e[b]+=[(i,a,c)] from heapq import heappush,heappop X=10**10 v=[X]*(1<<k)*n v[0*n+0]=0 q=[(0*n+0,0)] while len(q)>0: sc,s=heappop(q) if sc>v[s]: continue sp,sy=divmod(s,n) for i,ty,tc in e[sy]: if r[i]!=-1: tp=sp|(1<<r[i]) else: tp=sp t=tp*n+ty if v[t]>sc+tc: v[t]=sc+tc heappush(q,(v[t],t)) print(v[((1<<k)-1)*n+n-1])