結果

問題 No.788 トラックの移動
コンテスト
ユーザー ckawatak
提出日時 2019-02-24 23:20:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,029 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 233,444 KB
最終ジャッジ日時 2024-12-24 03:15:54
合計ジャッジ時間 21,007 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 9 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

from queue import PriorityQueue

N,M,L = list(map(int, input().split(' ')))
T = list(map(int, input().split(' ')))

E = []
for _ in range(N):
    E.append([])

for _ in range(M):
    a,b,c = list(map(int, input().split(' ')))
    E[a-1].append((b-1,c))
    E[b-1].append((a-1,c))

D = []
for _ in range(N):
    D.append([float('inf') for _ in range(N)])
    
for i in range(N):
    D[i][i] = 0
    
    que = PriorityQueue()
    que.put((0,i))
    while not que.empty():
        cost,current = que.get()
        if D[i][current] != cost:
            continue
        for e in E[current]:
            if D[i][current] + e[1] < D[i][e[0]]:
                D[i][e[0]] = D[i][current] + e[1]
                que.put((D[i][e[0]], e[0]))

answer = float('inf')                
for i in range(N):
    start = float('inf')    
    total = 0
    for j in range(N):
        if T[j]:
            total = total + T[j] * D[i][j] * 2
            start = min(start, D[L][j] - D[j][i])
    answer = min(answer, start + total)

print(answer)
0