結果

問題 No.17 2つの地点に泊まりたい
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:11:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 157 ms / 5,000 ms
コード長 1,451 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 81,984 KB
実行使用メモリ 77,752 KB
最終ジャッジ日時 2025-03-20 21:11:17
合計ジャッジ時間 3,634 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq

def main():
    n = int(input())
    s = [int(input()) for _ in range(n)]
    m = int(input())
    adj = [[] for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        adj[a].append((b, c))
        adj[b].append((a, c))
    
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
        heap = [(0, i)]
        while heap:
            cost, u = heapq.heappop(heap)
            if cost > dist[i][u]:
                continue
            for v, c in adj[u]:
                if dist[i][v] > dist[i][u] + c:
                    dist[i][v] = dist[i][u] + c
                    heapq.heappush(heap, (dist[i][v], v))
    
    min_total = INF
    destination = n - 1
    for u in range(1, destination):
        for v in range(1, destination):
            if u == v:
                continue
            su = s[u]
            sv = s[v]
            cost1 = dist[0][u] + dist[u][v] + dist[v][destination]
            valid1 = cost1 < INF
            cost1 = cost1 + su + sv if valid1 else INF
            
            cost2 = dist[0][v] + dist[v][u] + dist[u][destination]
            valid2 = cost2 < INF
            cost2 = cost2 + su + sv if valid2 else INF
            
            current_min = min(cost1, cost2)
            if current_min < min_total:
                min_total = current_min
    print(min_total)

if __name__ == '__main__':
    main()
0