結果
問題 | No.1812 Uribo Road |
ユーザー |
![]() |
提出日時 | 2024-11-22 11:33:28 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 779 bytes |
コンパイル時間 | 283 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 919,936 KB |
最終ジャッジ日時 | 2024-11-22 11:34:55 |
合計ジャッジ時間 | 74,086 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 MLE * 2 |
other | AC * 13 TLE * 6 MLE * 11 |
ソースコード
n,m,k=map(int,input().split())r=list(map(int,input().split()))for i in range(k):r[i]-=1e=[[[] for j in range(n)] for i in range(1<<k)]for i in range(m):a,b,c=map(int,input().split())a-=1b-=1for j in range(1<<k):if i not in r:e[j][a]+=[(j,b,c)]e[j][b]+=[(j,a,c)]else:p=r.index(i)if (j>>p)&1==0:e[j][a]+=[(j|(1<<p),b,c)]e[j][b]+=[(j|(1<<p),a,c)]else:e[j][a]+=[(j,b,c)]e[j][b]+=[(j,a,c)]from heapq import heappush,heappopX=10**10v=[[X]*n for i in range(1<<k)]v[0][0]=0q=[(0,0,0)]while len(q)>0:sc,sp,sy=heappop(q)if sc>v[sp][sy]:continuefor tp,ty,tc in e[sp][sy]:if v[tp][ty]>sc+tc:v[tp][ty]=sc+tcheappush(q,(v[tp][ty],tp,ty))print(v[-1][-1])