結果
問題 | 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 sys import heapq as hq input = sys.stdin.readline INF = 4611686018427387903 N, 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 -= 1 edges[i] = [x, y, z] graph[x].append((y, z)) graph[y].append((x, z)) def dijkstra(sv, graph): que = [(0, sv)] dp = [INF] * N while(que): d, v = hq.heappop(que) if(dp[v] <= d): continue dp[v] = d for nv, nd in graph[v]: hq.heappush(que, (d + nd, nv)) return dp V = 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)): continue for t in range(K): if(bit & (1 << t)): continue nbit = 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] + c if(dp[nbit][t][y] <= d): continue dp[nbit][t][y] = d ans = INF for i in range(K): for j in range(2): d = dp[-1][i][j] + dist[edges[R[i]][j]][N - 1] if(ans <= d): continue ans = d print(ans)