結果

問題 No.1308 ジャンプビーコン
ユーザー lam6er
提出日時 2025-04-09 21:00:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,911 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 82,716 KB
実行使用メモリ 78,964 KB
最終ジャッジ日時 2025-04-09 21:01:17
合計ジャッジ時間 10,207 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 WA * 9 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, Q, C = map(int, sys.stdin.readline().split())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v, l = map(int, sys.stdin.readline().split())
        edges[u].append((v, l))
        edges[v].append((u, l))
    X = list(map(int, sys.stdin.readline().split()))

    # Precompute all pairs' distances
    dist = [[-1]*(N+1) for _ in range(N+1)]
    for s in range(1, N+1):
        q = deque()
        q.append(s)
        dist[s][s] = 0
        while q:
            u = q.popleft()
            for v, l in edges[u]:
                if dist[s][v] == -1:
                    dist[s][v] = dist[s][u] + l
                    q.append(v)

    # Precompute paths (using BFS for path reconstruction)
    parent = [[0]*(N+1) for _ in range(N+1)]
    for s in range(1, N+1):
        q = deque()
        q.append(s)
        visited = [False]*(N+1)
        visited[s] = True
        parent[s][s] = -1
        while q:
            u = q.popleft()
            for v, _ in edges[u]:
                if not visited[v]:
                    visited[v] = True
                    parent[s][v] = u
                    q.append(v)

    def get_path(s, t):
        path = []
        v = t
        while v != s:
            path.append(v)
            v = parent[s][v]
            if v == -1:
                break
        path.append(s)
        path.reverse()
        return path

    current_dp = {}
    current_dp[None] = 0

    for i in range(Q-1):
        s = X[i]
        t = X[i+1]
        next_dp = {}
        path = get_path(s, t)
        beacon_candidates = set(path)

        min_u = None
        if i+2 < Q:
            next_t = X[i+2]
            min_cost = float('inf')
            for u in beacon_candidates:
                cost = C + dist[u][next_t]
                if cost < min_cost:
                    min_cost = cost
                    min_u = u

        for prev_b in current_dp:
            cost = current_dp[prev_b]

            # Option 1: Use beacon
            if prev_b is not None:
                new_cost = cost + C + dist[prev_b][t]
                if None not in next_dp or new_cost < next_dp[None]:
                    next_dp[None] = new_cost

            # Option 2: Move without changing beacon
            new_cost = cost + dist[s][t]
            key = prev_b
            if key not in next_dp or new_cost < next_dp[key]:
                next_dp[key] = new_cost

            # Option 3: Place beacon at u along the path
            for u in beacon_candidates:
                new_cost_opt3 = cost + dist[s][t]
                key_opt3 = u
                if key_opt3 not in next_dp or new_cost_opt3 < next_dp[key_opt3]:
                    next_dp[key_opt3] = new_cost_opt3

        current_dp = next_dp

    print(min(current_dp.values()))

if __name__ == '__main__':
    main()
0