結果
問題 | No.1812 Uribo Road |
ユーザー |
![]() |
提出日時 | 2024-11-30 20:45:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,111 ms / 5,000 ms |
コード長 | 1,714 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 81,720 KB |
実行使用メモリ | 120,572 KB |
最終ジャッジ日時 | 2024-11-30 20:45:37 |
合計ジャッジ時間 | 13,643 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
import sysimport heapq as hqinput = sys.stdin.readlineINF = 4611686018427387903N, M, K = map(int, input().split())R = [x - 1 for x in map(int, input().split())]edges = [[] for _ in [0] * M]graph = [[] for _ in [0] * N]for i in range(M):x, y, z = map(int, input().split())x -= 1; y -= 1edges[i] = [x, y, z]graph[x].append((y, z))graph[y].append((x, z))def dijkstra(sv, graph):que = [(0, sv)]dp = [INF] * Nwhile(que):d, v = hq.heappop(que)if(dp[v] <= d):continuedp[v] = dfor nv, nd in graph[v]:hq.heappush(que, (d + nd, nv))return dpV = set([0, N - 1])for r in R:V.add(edges[r][0])V.add(edges[r][1])dist = [[] for _ in [0] * N]for sv in V:dist[sv] = dijkstra(sv, graph)dp = [[[INF] * 2 for _ in [0] * K] for _ in [0] * (1 << K)]for i in range(K):for j in range(2):dp[1 << i][i][j] = dist[0][edges[R[i]][j ^ 1]] + edges[R[i]][2]for bit in range(1, 1 << K):for s in range(K):if not(bit & (1 << s)):continuefor t in range(K):if(bit & (1 << t)):continuenbit = bit | (1 << t)c = edges[R[t]][2]for x in range(2):for y in range(2):p = edges[R[s]][x]; q = edges[R[t]][y ^ 1]d = dp[bit][s][x] + dist[p][q] + cif(dp[nbit][t][y] <= d):continuedp[nbit][t][y] = dans = INFfor i in range(K):for j in range(2):d = dp[-1][i][j] + dist[edges[R[i]][j]][N - 1]if(ans <= d):continueans = dprint(ans)