結果

問題 No.1812 Uribo Road
ユーザー qib
提出日時 2022-10-30 20:22:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 978 ms / 5,000 ms
コード長 1,654 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 81,716 KB
実行使用メモリ 111,348 KB
最終ジャッジ日時 2024-07-07 12:18:52
合計ジャッジ時間 12,335 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
import heapq

INF = 1 << 60

n, m, k = map(int, input().split())
r = list(map(int, input().split()))
r.sort()

roads = deque()
g = [[] for _ in range(n)]
for i in range(m):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  g[a].append((b, c))
  g[b].append((a, c))
  if len(roads) < k and r[len(roads)] == i + 1:
    roads.append((a, b, c))

roads.appendleft((0, 0, 0))
roads.appendleft((n - 1, n - 1, 0))

idx = {}
vs = []
for a, b, _ in roads:
  for v in [a, b]:
    if idx.get(v, None) is None:
      idx[v] = len(idx)
      vs.append(v)

dist = [[INF for _ in range(len(idx))] for _ in range(len(idx))]
for src in vs:
  d = [INF for _ in range(n)]
  d[src] = 0
  hp = [(0, src)]
  while len(hp) > 0:
    cd, cur = heapq.heappop(hp)
    if cd > d[cur]:
      continue
    for nxt, cost in g[cur]:
      if d[nxt] > d[cur] + cost:
        d[nxt] = d[cur] + cost
        heapq.heappush(hp, (d[nxt], nxt))

  for dst in vs:
    dist[idx[src]][idx[dst]] = d[dst]

dp = [[[INF for _ in range(2)] for _ in range(k + 2)] for _ in range(1 << (k + 2))]
dp[1][0][0] = 0
dp[1][0][1] = 0
for mask in range(1 << (k + 2)):
  dpm = dp[mask]
  for cur in range(k + 2):
    s, t, _ = roads[cur]
    for nxt in range(k + 2):
      if (mask >> nxt) & 1 != 0:
        continue
      u, v, c = roads[nxt]

      dp[mask | (1 << nxt)][nxt][0] = min(dp[mask | (1 << nxt)][nxt][0], dpm[cur][0] + dist[idx[s]][idx[v]] + c, dpm[cur][1] + dist[idx[t]][idx[v]] + c)
      dp[mask | (1 << nxt)][nxt][1] = min(dp[mask | (1 << nxt)][nxt][1], dpm[cur][0] + dist[idx[s]][idx[u]] + c, dpm[cur][1] + dist[idx[t]][idx[u]] + c)

print(min(dp[-1][1]))
0