結果
問題 | No.1812 Uribo Road |
ユーザー |
|
提出日時 | 2022-10-23 20:16:52 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,340 bytes |
コンパイル時間 | 133 ms |
コンパイル使用メモリ | 82,340 KB |
実行使用メモリ | 459,624 KB |
最終ジャッジ日時 | 2024-07-02 10:38:32 |
合計ジャッジ時間 | 8,945 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 8 TLE * 1 -- * 21 |
ソースコード
import sysreadline = sys.stdin.readline# dp[v][S] = 今までに触った猪の集合がSでvにいるときの最小コストN,M,K = map(int,readline().split())R = list(map(int,readline().split()))Rdic = {} # 道の番号から猪の番号を導くfor i in range(K):Rdic[R[i] - 1] = iG = [[] for i in range(N)]for i in range(M):a,b,c = map(int,readline().split())ino = -1if i in Rdic: # 道の番号が含まれるino = Rdic[i] # イノシシの番号に変換G[a - 1].append([b - 1, c, ino])G[b - 1].append([a - 1, c, ino])INF = 1 << 60best = [[INF] * (1 << K) for i in range(N)]import heapq as hqq = []hq.heappush(q, (0, 0, 0)) # 距離、頂点、今までに触った猪の集合complete = (1 << K) - 1while q:d,v,status = hq.heappop(q)if best[v][status] < d:continuebest[v][status] = dif v == N - 1 and status == complete:print(best[v][status])breakfor child, cost, ino in G[v]:if ino != -1:next_status = status | (1 << ino)if best[child][next_status] <= d + cost:continuebest[child][next_status] = d + costhq.heappush(q, (d + cost, child, status | (1 << ino)))else:if best[child][status] <= d + cost:continuebest[child][status] = d + costhq.heappush(q, (d + cost, child, status))