def solve(N, M, X, S, ABC): INF = 1e+99 from collections import defaultdict edges = defaultdict(dict) for A, B, C in ABC: edges[A - 1][B - 1] = C edges[B - 1][A - 1] = C warps = [[], [], []] for i in range(N): warps[S[i]].append(i) usedWarp = set() GOAL = N - 1 START = 0 from heapq import heappush, heappop, heapify queue = [(0, START)] mincost = [INF] * N mincost[START] = 0 visited = [0] * N while True: cost, pos = heappop(queue) if pos == GOAL: return cost if visited[pos]: continue visited[pos] = 1 ep = edges[pos] for next in ep: nc = cost + ep[next] if nc < mincost[next]: mincost[next] = nc heappush(queue, (nc, next)) for typ in range(3): if typ == S[pos]: continue warp = S[pos] + typ - 1 if (S[pos], typ) in usedWarp: continue c = X[warp] usedWarp.add((S[pos], typ)) nc = cost + c for next in warps[typ]: if nc < mincost[next]: mincost[next] = nc heappush(queue, (nc, next))