結果

問題 No.1308 ジャンプビーコン
ユーザー gew1fw
提出日時 2025-06-12 14:34:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,097 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,844 KB
実行使用メモリ 474,588 KB
最終ジャッジ日時 2025-06-12 14:35:25
合計ジャッジ時間 42,328 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 37
権限があれば一括ダウンロードができます

ソースコード

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))
    query = list(map(int, sys.stdin.readline().split()))
    x = query
    steps = []
    for i in range(Q-1):
        a = x[i]
        b = x[i+1]
        steps.append((a, b))
    
    # Precompute distances using BFS for each node
    dist = {}
    for u in range(1, N+1):
        q = deque()
        q.append(u)
        visited = {u: 0}
        while q:
            v = q.popleft()
            for nei, l in edges[v]:
                if nei not in visited:
                    visited[nei] = visited[v] + l
                    q.append(nei)
        dist[u] = visited
    
    # Now, for each step, get the distance
    distances = []
    for a, b in steps:
        distances.append(dist[a][b])
    
    # Initialize DP
    dp = [[float('inf')] * 2 for _ in range(Q+1)]
    dp[1][0] = 0  # No beacon at x1
    dp[1][1] = 0  # Beacon at x1
    
    for i in range(1, Q):
        if i >= len(distances):
            break
        d_ij = distances[i-1]
        for s in [0, 1]:
            if dp[i][s] == float('inf'):
                continue
            # Option 1: move normally
            new_cost = dp[i][s] + d_ij
            # After moving, can choose to set beacon or not at x_{i+1}
            for s_new in [0, 1]:
                if new_cost < dp[i+1][s_new]:
                    dp[i+1][s_new] = new_cost
            # Option 2: if s ==1, use the beacon
            if s == 1:
                # The movement cost is min(d_ij, C)
                cost = min(d_ij, C)
                for s_new in [0, 1]:
                    if dp[i][s] + cost < dp[i+1][s_new]:
                        dp[i+1][s_new] = dp[i][s] + cost
    
    # Find the minimal cost after all steps
    min_cost = min(dp[Q][0], dp[Q][1])
    print(min_cost)

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