結果

問題 No.788 トラックの移動
ユーザー htkbhtkb
提出日時 2019-02-08 22:24:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,282 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 152,900 KB
最終ジャッジ日時 2024-07-01 11:37:11
合計ジャッジ時間 6,693 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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 # 

import sys
from itertools import starmap
from operator import mul

N, M, L = map(int, input().split())
L -= 1
t = list(map(int, input().split()))
matrix = [[float("inf")]*N for _ in [0]*N]
for i in range(N):
    matrix[i][i] = 0

for a, b, c in ((map(int, l.split())) for l in sys.stdin):
    matrix[a-1][b-1] = matrix[b-1][a-1] = c

def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    :param v_count: 頂点数
    :param matrix: 隣接行列(到達不能はfloat("inf"))
    """
    # 到達不能をfloat("inf")にしておけば余計なチェックを入れなくても
    # inf > inf+(-1) のような到達不能＋負辺が繋がってしまうことはない
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix

edges = warshall_floyd(N, matrix)

ans = float("inf")
for i in range(N):
    cost = sum(starmap(mul, zip(matrix[i], t))) * 2
    if t[L] > 0:
        cost -= matrix[i][L]
    else:
        cost += min(matrix[i][L], min(matrix[L][j]-matrix[j][i] for j in range(N) if t[j]))
    if ans > cost:
        ans = cost

print(ans)
0