結果

問題 No.17 2つの地点に泊まりたい
ユーザー maspy
提出日時 2020-03-05 10:46:55
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 920 ms / 5,000 ms
コード長 703 bytes
コンパイル時間 82 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 56,264 KB
最終ジャッジ日時 2024-10-14 00:52:07
合計ジャッジ時間 29,036 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
外部呼び出し有り
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
# %%
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from scipy.sparse.csgraph import floyd_warshall
import numpy as np

# %%
N = int(readline())
S = np.array([readline() for _ in range(N)], np.int64)
M = int(readline())
ABC = np.array(read().split(), np.int64)
A = ABC[::3]
B = ABC[1::3]
C = ABC[2::3]

# %%
graph = np.full((N, N), np.inf)
graph[A, B] = C


# %%
dist_mat = floyd_warshall(graph, directed=False)

# %%
cost = dist_mat[0, :][:, None] + S[:, None] + dist_mat + S[None, :] + dist_mat[N - 1, :][None, :]
np.fill_diagonal(cost, np.inf)
cost = cost[1:-1, 1:-1]
answer = int(cost.min())
print(answer)
0