結果

問題 No.788 トラックの移動
ユーザー ckawatakckawatak
提出日時 2019-02-24 23:52:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,036 bytes
コンパイル時間 140 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 153,324 KB
最終ジャッジ日時 2024-06-06 12:51:26
合計ジャッジ時間 6,549 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

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] != 0:
            total = total + T[j] * D[i][j] * 2
            start = min(start, D[L-1][j] - D[j][i])
    answer = min(answer, start + total)

print(answer)
0