結果

問題 No.1812 Uribo Road
ユーザー tobusakanatobusakana
提出日時 2022-10-23 21:12:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,920 ms / 5,000 ms
コード長 3,455 bytes
コンパイル時間 2,349 ms
コンパイル使用メモリ 86,756 KB
実行使用メモリ 120,024 KB
最終ジャッジ日時 2023-09-15 06:41:28
合計ジャッジ時間 23,727 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
71,332 KB
testcase_01 AC 79 ms
71,440 KB
testcase_02 AC 84 ms
75,440 KB
testcase_03 AC 303 ms
80,712 KB
testcase_04 AC 77 ms
71,260 KB
testcase_05 AC 76 ms
71,372 KB
testcase_06 AC 82 ms
76,008 KB
testcase_07 AC 143 ms
77,908 KB
testcase_08 AC 209 ms
79,244 KB
testcase_09 AC 269 ms
81,112 KB
testcase_10 AC 199 ms
79,072 KB
testcase_11 AC 208 ms
79,132 KB
testcase_12 AC 1,379 ms
101,952 KB
testcase_13 AC 690 ms
96,112 KB
testcase_14 AC 648 ms
94,516 KB
testcase_15 AC 676 ms
91,916 KB
testcase_16 AC 544 ms
85,508 KB
testcase_17 AC 1,276 ms
100,216 KB
testcase_18 AC 1,099 ms
99,420 KB
testcase_19 AC 1,920 ms
114,432 KB
testcase_20 AC 1,842 ms
114,524 KB
testcase_21 AC 1,837 ms
120,024 KB
testcase_22 AC 1,773 ms
114,972 KB
testcase_23 AC 348 ms
82,048 KB
testcase_24 AC 97 ms
76,428 KB
testcase_25 AC 369 ms
84,676 KB
testcase_26 AC 219 ms
79,192 KB
testcase_27 AC 762 ms
92,720 KB
testcase_28 AC 477 ms
86,944 KB
testcase_29 AC 78 ms
71,488 KB
testcase_30 AC 303 ms
81,484 KB
testcase_31 AC 1,255 ms
96,268 KB
testcase_32 AC 231 ms
79,488 KB
testcase_33 AC 596 ms
90,712 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 本質的には猪のいる道の両端の頂点の情報さえ分かればよい。
# それらの頂点間の最短距離を求める。
# グラフとしては、それらの頂点間だけに辺を貼ったものを作る。

import sys
readline = sys.stdin.readline

N,M,K = map(int,readline().split())
R = list(map(int,readline().split()))
Rdic = {} # 道番号->猪の番号へのdictionary
for i in range(K):
  Rdic[R[i] - 1] = i
  
# まず通常のグラフを作成する。
G = [[] for i in range(N)]
# 重要な頂点
points = set()
points.add(0)
points.add(N - 1)
ino_road = {}
for i in range(M):
  a,b,c = map(int,readline().split())
  a -= 1
  b -= 1
  # イノシシのいる道か？
  ino = -1
  if i in Rdic:
    ino = Rdic[i] # イノシシの番号
    points.add(a) # 重要な頂点として追加
    points.add(b)
    if a > b:
      a,b = b,a
    ino_road[(a, b)] = [c, ino]
  G[a].append([b, c, ino])
  G[b].append([a, c, ino])

points = sorted(points)
L = len(points) # 重要な頂点の数
# 重要な頂点->元の頂点、元の頂点->重要な頂点への変換
# 重要な頂点番号 -> 元の頂点番号への変換はpoints[重要な頂点番号]
Pdic = {}
for i in range(L):
  Pdic[points[i]] = i
# 元の頂点->重要な頂点番号への変換はPdic[元の頂点番号]

import heapq as hq
R = [[] for i in range(L)] # 重要な頂点のみのグラフ
# まず、猪がいる道には必ず道路を引く。
for key, value in ino_road.items():
  a_ind = Pdic[key[0]]
  b_ind = Pdic[key[1]]
  R[a_ind].append([b_ind, value[0], value[1]])
  R[b_ind].append([a_ind, value[0], value[1]])

for start in range(L): # 頂点を変えてのダイクストラ
  s = points[start] # 元のグラフでの重要な頂点番号
  # Gに対してのダイクストラ
  visited = [False] * N # 訪問済みの管理
  q = []
  hq.heappush(q, (0, s)) # コスト、頂点
  while q:
    d, v = hq.heappop(q)
    if visited[v]:
      continue
    visited[v] = True
    if v in Pdic: # 重要な頂点である場合
      imp = Pdic[v] # 重要な頂点番号
      if start != imp and start < imp and (start, imp) not in ino_road:
        R[start].append([imp, d, -1])
        R[imp].append([start, d, -1])
    for child, cost, ino in G[v]:
      if visited[child]:
        continue
      hq.heappush(q, (d + cost, child))
      
# Rが重要な頂点同士のグラフになった。
# あとは、このグラフで
# dp[v][S] = 今いる頂点v, 逢った猪の集合S
# をやる。
start = Pdic[0]
goal = Pdic[N - 1]

dp = [[False] * (1 << K) for i in range(L)]
INF = 1 << 60
best = [[INF] * (1 << K) for i in range(L)]
q = []
hq.heappush(q, (0, 0, 0)) # 距離、頂点、今までにあった猪の集合
complete = (1 << K) - 1
while q:
  d, v, ino_status = hq.heappop(q)
  if dp[v][ino_status]:
    continue
  dp[v][ino_status] = True
  if v == goal and ino_status == complete:
    print(d)
    break
  for child, cost, ino in R[v]:
    if ino != -1: # イノシシに出会う場合
      next_status = ino_status | (1 << ino)
      if dp[child][next_status] or best[child][next_status] <= d + cost:
        continue
      best[child][next_status] = d + cost
      hq.heappush(q, (d + cost, child, next_status))
    else:
      if dp[child][ino_status] or best[child][ino_status] <= d + cost:
        continue
      best[child][ino_status] = d + cost
      hq.heappush(q, (d + cost, child, ino_status))
0