結果

問題 No.1812 Uribo Road
ユーザー tobusakanatobusakana
提出日時 2022-10-23 21:12:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,605 ms / 5,000 ms
コード長 3,455 bytes
コンパイル時間 1,058 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 117,496 KB
最終ジャッジ日時 2024-07-02 11:14:33
合計ジャッジ時間 20,182 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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