結果

問題 No.788 トラックの移動
ユーザー lam6er
提出日時 2025-04-16 15:34:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,922 ms / 2,000 ms
コード長 1,952 bytes
コンパイル時間 419 ms
コンパイル使用メモリ 82,096 KB
実行使用メモリ 143,312 KB
最終ジャッジ日時 2025-04-16 15:39:00
合計ジャッジ時間 12,019 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

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]) -1  # convert to 0-based
    idx +=1
    
    t = list(map(int, data[idx:idx+N]))
    idx +=N
    
    # Build adjacency list
    adj = [[] for _ in range(N)]
    for _ in range(M):
        a = int(data[idx])-1
        idx +=1
        b = int(data[idx])-1
        idx +=1
        c = int(data[idx])
        idx +=1
        adj[a].append( (b, c) )
        adj[b].append( (a, c) )
    
    # Precompute all-pairs shortest paths using Dijkstra's algorithm
    INF = float('inf')
    dist = [ [INF]*N for _ in range(N) ]
    for start in range(N):
        dist[start][start] = 0
        heap = [ (0, start) ]
        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[start][u]:
                continue
            for v, w in adj[u]:
                if dist[start][v] > d + w:
                    dist[start][v] = d + w
                    heapq.heappush(heap, (dist[start][v], v))
    
    min_total = INF
    total_trucks = sum(t)
    
    for X in range(N):
        sum_trucks = total_trucks - t[X]
        if sum_trucks == 0:
            current_cost = 0
        else:
            sum_part = 0
            min_part = INF
            has_any = False
            for Y in range(N):
                if Y == X or t[Y] == 0:
                    continue
                sum_part += 2 * t[Y] * dist[Y][X]
                current = dist[L][Y] - dist[Y][X]
                if current < min_part:
                    min_part = current
                has_any = True
            if not has_any:
                current_cost = 0
            else:
                current_cost = sum_part + min_part
        if current_cost < min_total:
            min_total = current_cost
    
    print(min_total)

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