結果

問題 No.1308 ジャンプビーコン
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:50:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,013 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 82,140 KB
実行使用メモリ 77,712 KB
最終ジャッジ日時 2025-05-14 12:51:37
合計ジャッジ時間 16,053 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 distance between all pairs using BFS for each node
    dist = [[0]*(N+1) for _ in range(N+1)]
    for u in range(1, N+1):
        d = [-1]*(N+1)
        d[u] = 0
        q = deque([u])
        while q:
            v = q.popleft()
            for to, l in edges[v]:
                if d[to] == -1 or d[to] > d[v] + l:
                    d[to] = d[v] + l
                    q.append(to)
        for v in range(1, N+1):
            dist[u][v] = d[v]
    
    # DP: current beacon position -> min time
    # beacon position is -1 if not exists
    current = { -1: 0 }
    for i in range(Q-1):
        src = x[i]
        dst = x[i+1]
        next_dp = {}
        for b_prev, time_prev in current.items():
            # Option 1: move normally
            cost = dist[src][dst]
            key = b_prev
            if key not in next_dp or next_dp[key] > time_prev + cost:
                next_dp[key] = time_prev + cost
            
            # Option 2: if beacon exists, use jump
            if b_prev != -1:
                cost = C + dist[b_prev][dst]
                key = -1
                if key not in next_dp or next_dp[key] > time_prev + cost:
                    next_dp[key] = time_prev + cost
            
            # Option 3: place beacon at any a and move
            for a in range(1, N+1):
                cost = dist[src][a] + dist[a][dst]
                key = a
                if key not in next_dp or next_dp[key] > time_prev + cost:
                    next_dp[key] = time_prev + cost
        current = next_dp
    
    print(min(current.values()))

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