結果

問題 No.788 トラックの移動
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:34:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,693 bytes
コンパイル時間 438 ms
コンパイル使用メモリ 81,552 KB
実行使用メモリ 87,376 KB
最終ジャッジ日時 2025-04-16 15:39:30
合計ジャッジ時間 10,522 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    L = int(data[idx]); idx += 1
    t = list(map(int, data[idx:idx+N]))
    idx += N
    adj = [[] for _ in range(N+1)]  # 1-based indexing
    for _ in range(M):
        a = int(data[idx]); idx += 1
        b = int(data[idx]); idx += 1
        c = int(data[idx]); idx += 1
        adj[a].append((b, c))
        adj[b].append((a, c))
    
    # Precompute distances from L
    def dijkstra(start):
        INF = 1 << 60
        dist = [INF] * (N + 1)
        dist[start] = 0
        heap = [(0, start)]
        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u]:
                continue
            for v, c in adj[u]:
                if dist[v] > d + c:
                    dist[v] = d + c
                    heapq.heappush(heap, (dist[v], v))
        return dist
    
    d_L = dijkstra(L)
    
    # List of nodes with t_i > 0
    nodes_with_t = [i + 1 for i in range(N) if t[i] > 0]
    if not nodes_with_t:
        print(0)
        return
    
    min_total = float('inf')
    
    for X in range(1, N + 1):
        # Compute distances from X
        dist_X = dijkstra(X)
        sum_2d = 0
        min_term = float('inf')
        for i in nodes_with_t:
            sum_2d += 2 * dist_X[i] * t[i - 1]
            current_term = d_L[i] - dist_X[i]
            if current_term < min_term:
                min_term = current_term
        total = sum_2d + min_term
        if total < min_total:
            min_total = total
    
    print(min_total)

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