結果

問題 No.848 なかよし旅行
コンテスト
ユーザー tcltk
提出日時 2021-01-31 04:34:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,567 bytes
コンパイル時間 311 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 247,552 KB
最終ジャッジ日時 2024-06-28 15:30:53
合計ジャッジ時間 7,035 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#region Header
#!/usr/bin/env python3
# from typing import *

import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
    return sys.stdin.readline()[:-1]

sys.setrecursionlimit(1000000)
#endregion

# _INPUT = """# paste here...
# """
# sys.stdin = io.StringIO(_INPUT)


def main():
    N, M, P, Q, T = map(int, input().split())
    P -= 1
    Q -= 1
    G = [list() for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a-1].append((b-1, c))
        G[b-1].append((a-1, c))

    dist = [[10**20] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0

    for start in range(N):

        # Dijkstra
        hq = []
        heapq.heappush(hq, (0, start))
        while hq:
            d, p = heapq.heappop(hq)
            if d > dist[start][p]:
                continue
            for (p1, w1) in G[p]:
                d1 = dist[start][p] + w1
                if d1 < dist[start][p1]:
                    dist[start][p1] = d1
                    heapq.heappush(hq, (dist[start][p1], p1))

    if dist[0][P] + dist[P][Q] + dist[Q][0] <= T:
        print(T)
    else:
        max_shared_time = -1
        for i in range(N):
            if 2 * (dist[0][i] + max(dist[i][P], dist[i][Q])) <= T:
                t = T - 2 * max(dist[i][P], dist[i][Q])
                max_shared_time = max(max_shared_time, t)
        print(max_shared_time)


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