結果
問題 | No.1812 Uribo Road |
ユーザー |
![]() |
提出日時 | 2024-11-22 11:41:37 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 590 bytes |
コンパイル時間 | 201 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 238,976 KB |
最終ジャッジ日時 | 2024-11-22 11:41:42 |
合計ジャッジ時間 | 4,550 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 RE * 1 |
other | AC * 6 RE * 24 |
ソースコード
n,m,k=map(int,input().split())r=[-1]*(1<<k)for i,v in enumerate(list(map(int,input().split()))):r[v-1]=ie=[[] for i in range(n)]for i in range(m):a,b,c=map(int,input().split())a-=1b-=1e[a]+=[(i,b,c)]e[b]+=[(i,a,c)]from heapq import heappush,heappopX=10**10v=[X]*(1<<k)*nv[0*n+0]=0q=[(0*n+0,0)]while len(q)>0:sc,s=heappop(q)if sc>v[s]:continuesp,sy=divmod(s,n)for i,ty,tc in e[sy]:if r[i]!=-1:tp=sp|(1<<r[i])else:tp=spt=tp*n+tyif v[t]>sc+tc:v[t]=sc+tcheappush(q,(v[t],t))print(v[((1<<k)-1)*n+n-1])