結果

問題 No.17 2つの地点に泊まりたい
ユーザー mlihua09mlihua09
提出日時 2020-09-13 02:46:39
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 881 ms / 5,000 ms
コード長 510 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 56,648 KB
最終ジャッジ日時 2024-06-10 19:39:41
合計ジャッジ時間 27,845 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
外部呼び出し有り
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 794 ms
56,264 KB
testcase_01 AC 832 ms
56,004 KB
testcase_02 AC 857 ms
56,388 KB
testcase_03 AC 819 ms
56,512 KB
testcase_04 AC 820 ms
56,268 KB
testcase_05 AC 815 ms
54,260 KB
testcase_06 AC 819 ms
54,376 KB
testcase_07 AC 815 ms
55,896 KB
testcase_08 AC 819 ms
54,020 KB
testcase_09 AC 854 ms
54,520 KB
testcase_10 AC 870 ms
56,260 KB
testcase_11 AC 839 ms
56,188 KB
testcase_12 AC 820 ms
56,380 KB
testcase_13 AC 821 ms
56,268 KB
testcase_14 AC 823 ms
56,276 KB
testcase_15 AC 809 ms
56,272 KB
testcase_16 AC 797 ms
56,648 KB
testcase_17 AC 799 ms
56,140 KB
testcase_18 AC 823 ms
56,520 KB
testcase_19 AC 831 ms
56,140 KB
testcase_20 AC 818 ms
56,268 KB
testcase_21 AC 879 ms
56,168 KB
testcase_22 AC 881 ms
56,512 KB
testcase_23 AC 842 ms
54,372 KB
testcase_24 AC 831 ms
56,264 KB
testcase_25 AC 809 ms
56,012 KB
testcase_26 AC 833 ms
54,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())

from scipy.sparse.csgraph import shortest_path

import numpy as np

S = np.array([int(input()) for i in range(N)])

D = np.zeros((N, N), dtype=int)

M = int(input())

for i in range(M):
    a, b, c = map(int, input().split())
    
    D[a, b] = c
    D[b, a] = c
    
X = shortest_path(D, directed=False)

from itertools import permutations

ans = 10 ** 9

for i, j in permutations(range(1, N - 1), r=2):
    
    ans = min(ans, S[i] + S[j] + X[0, i] + X[i, j] + X[j, N - 1])
print(int(ans))
0