RedSpicaWS-7 Load to cocoa

問題

方針

スタート地点→商店→スパークリング黒ココアをゲット→スタート地点、の流れ。

world1: まだ商店に到達していない世界

world2: 商店には到達したけど、スパークリング黒ココアはゲットしていない世界

world3: 商店に到達してるし、スパークリング黒ココアもゲットしてる世界

の3つの世界を作って、商店のある地点はworld1→world2にいける長さ0の道を、スパークリング黒ココアのある地点はworld2→world3にいける長さ0の道を作る。

ダイクストラ法でがんばります。

world3の話をしてるときにworld1の辺の話をしたりしてるけど、計算量的に間に合うでしょって投げたらACだったのでokということで！！！！

ACコード

from heapq import heappop, heappush, heapify


# スタート位置s,頂点数n,各始点の[終点,コスト]
def dijkstra(s, n, lis):
    dist = [float('Inf')] * n
    dist[s] = 0
    que = [(0, s)]
    heapify(que)
    used = [False] * n
    while que:
        _, pos = heappop(que)
        if used[pos]:
            continue
        used[pos] = True
        for to, pcost in lis[pos]:
            cost = dist[pos] + pcost
            if dist[to] > cost:
                dist[to] = cost
                heappush(que, (cost, to))
    return dist


N, M = map(int, input().split())

# 0~N-1:中継点未到達, N~2N-1:中継点1到達済み, 2N~3N-1:中継点2到達済み
G = [[] for _ in range(N * 3)]
G[2 * N - 1].append((3 * N - 1, 0))
for _ in range(M):
    u, v, l = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append((v, l))
    G[v].append((u, l))
    G[u + N].append((v + N, l))
    G[v + N].append((u + N, l))
    G[u + N * 2].append((v + N * 2, l))
    G[v + N * 2].append((u + N * 2, l))
K = int(input())
P = [int(p) - 1 for p in input().split()]
for p in P:
    G[p].append((p + N, 0))

dist = dijkstra(0, N * 3, G)
print(dist[2 * N])