結果

問題 No.1308 ジャンプビーコン
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:22:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,460 bytes
コンパイル時間 332 ms
コンパイル使用メモリ 82,716 KB
実行使用メモリ 243,100 KB
最終ジャッジ日時 2025-04-24 12:24:18
合計ジャッジ時間 9,411 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 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 distance between all pairs using BFS for each node
    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 the path for each x[i] to x[i+1]
    # For each query, find the path from a to b
    # To find the path, use BFS and track parents
    def get_path(a, b):
        parent = [-1] * (N+1)
        q = deque()
        q.append(a)
        parent[a] = None
        while q:
            u = q.popleft()
            if u == b:
                break
            for v, l in edges[u]:
                if parent[v] == -1:
                    parent[v] = u
                    q.append(v)
        path = []
        u = b
        while u is not None:
            path.append(u)
            u = parent[u]
        return path[::-1]
    
    # Initialize DP
    dp = [dict() for _ in range(Q)]
    # dp[i][b] = min time to reach x[i] with beacon at b (b=0 means no beacon)
    dp[0][0] = 0
    
    for i in range(Q-1):
        current = x[i]
        next_node = x[i+1]
        path = get_path(current, next_node)
        path_set = set(path)
        current_dp = dp[i]
        next_dp = {}
        
        for prev_b in current_dp:
            current_time = current_dp[prev_b]
            
            # Option 1: Move normally, beacon remains prev_b (if exists)
            time_normal = dist[current][next_node]
            key = prev_b
            if key not in next_dp or current_time + time_normal < next_dp[key]:
                next_dp[key] = current_time + time_normal
            
            # Option 2: If there's a beacon, jump to it and then move
            if prev_b != 0:
                time_jump = C + dist[prev_b][next_node]
                key = 0
                if key not in next_dp or current_time + time_jump < next_dp[key]:
                    next_dp[key] = current_time + time_jump
            
            # Option 3: Place beacon at some node on the path
            for a in path:
                time_place = dist[current][a] + dist[a][next_node]
                key = a
                new_time = current_time + time_place
                if key not in next_dp or new_time < next_dp[key]:
                    next_dp[key] = new_time
            
            # Option 4: If there's a beacon, jump to it, then place beacon on path
            if prev_b != 0:
                for a in path:
                    time_jump_place = C + dist[prev_b][a] + dist[a][next_node]
                    key = a
                    new_time = current_time + time_jump_place
                    if key not in next_dp or new_time < next_dp[key]:
                        next_dp[key] = new_time
        
        dp[i+1] = next_dp
    
    # The answer is the minimum value in dp[Q-1]
    print(min(dp[Q-1].values()))

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