結果

問題 No.1812 Uribo Road
ユーザー qibqib
提出日時 2022-10-30 20:22:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,114 ms / 5,000 ms
コード長 1,654 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 87,228 KB
実行使用メモリ 113,872 KB
最終ジャッジ日時 2023-09-21 18:42:45
合計ジャッジ時間 15,906 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 93 ms
71,676 KB
testcase_01 AC 96 ms
72,256 KB
testcase_02 AC 128 ms
77,768 KB
testcase_03 AC 458 ms
99,748 KB
testcase_04 AC 91 ms
71,696 KB
testcase_05 AC 103 ms
77,116 KB
testcase_06 AC 111 ms
77,884 KB
testcase_07 AC 164 ms
80,928 KB
testcase_08 AC 202 ms
80,524 KB
testcase_09 AC 243 ms
80,820 KB
testcase_10 AC 185 ms
80,068 KB
testcase_11 AC 208 ms
79,328 KB
testcase_12 AC 710 ms
105,500 KB
testcase_13 AC 514 ms
102,196 KB
testcase_14 AC 523 ms
102,364 KB
testcase_15 AC 417 ms
85,080 KB
testcase_16 AC 420 ms
87,228 KB
testcase_17 AC 782 ms
99,344 KB
testcase_18 AC 574 ms
102,844 KB
testcase_19 AC 1,114 ms
113,872 KB
testcase_20 AC 1,053 ms
112,608 KB
testcase_21 AC 943 ms
110,236 KB
testcase_22 AC 799 ms
108,256 KB
testcase_23 AC 272 ms
83,976 KB
testcase_24 AC 124 ms
77,860 KB
testcase_25 AC 319 ms
81,940 KB
testcase_26 AC 206 ms
80,228 KB
testcase_27 AC 421 ms
90,556 KB
testcase_28 AC 407 ms
84,156 KB
testcase_29 AC 95 ms
71,956 KB
testcase_30 AC 241 ms
81,804 KB
testcase_31 AC 832 ms
106,492 KB
testcase_32 AC 210 ms
81,212 KB
testcase_33 AC 584 ms
104,168 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