結果

問題 No.1812 Uribo Road
ユーザー qibqib
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
54,912 KB
testcase_01 AC 42 ms
55,424 KB
testcase_02 AC 70 ms
74,112 KB
testcase_03 AC 380 ms
98,708 KB
testcase_04 AC 38 ms
54,660 KB
testcase_05 AC 49 ms
64,896 KB
testcase_06 AC 57 ms
69,248 KB
testcase_07 AC 111 ms
79,268 KB
testcase_08 AC 135 ms
78,224 KB
testcase_09 AC 182 ms
78,844 KB
testcase_10 AC 125 ms
77,924 KB
testcase_11 AC 144 ms
78,408 KB
testcase_12 AC 612 ms
102,960 KB
testcase_13 AC 458 ms
101,060 KB
testcase_14 AC 441 ms
101,516 KB
testcase_15 AC 343 ms
83,164 KB
testcase_16 AC 352 ms
85,728 KB
testcase_17 AC 685 ms
97,280 KB
testcase_18 AC 494 ms
101,408 KB
testcase_19 AC 978 ms
111,348 KB
testcase_20 AC 900 ms
110,284 KB
testcase_21 AC 799 ms
108,132 KB
testcase_22 AC 692 ms
105,664 KB
testcase_23 AC 206 ms
82,356 KB
testcase_24 AC 70 ms
74,588 KB
testcase_25 AC 239 ms
80,936 KB
testcase_26 AC 147 ms
78,388 KB
testcase_27 AC 331 ms
89,184 KB
testcase_28 AC 315 ms
81,840 KB
testcase_29 AC 42 ms
55,680 KB
testcase_30 AC 171 ms
79,800 KB
testcase_31 AC 717 ms
104,952 KB
testcase_32 AC 153 ms
79,752 KB
testcase_33 AC 499 ms
102,732 KB
権限があれば一括ダウンロードができます

ソースコード

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