結果

問題 No.848 なかよし旅行
ユーザー lam6er
提出日時 2025-04-16 00:03:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,663 bytes
コンパイル時間 472 ms
コンパイル使用メモリ 81,524 KB
実行使用メモリ 116,188 KB
最終ジャッジ日時 2025-04-16 00:05:02
合計ジャッジ時間 5,329 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def dijkstra(n, graph, start):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))
    
    while heap:
        current_dist, u = heapq.heappop(heap)
        if current_dist > dist[u]:
            continue
        for v, c in graph[u]:
            if dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
                heapq.heappush(heap, (dist[v], v))
    return dist

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx]); idx +=1
    m = int(data[idx]); idx +=1
    P = int(data[idx]); idx +=1
    Q = int(data[idx]); idx +=1
    T = int(data[idx]); idx +=1
    
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a = int(data[idx]); idx +=1
        b = int(data[idx]); idx +=1
        c = int(data[idx]); idx +=1
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    d1 = dijkstra(n, graph, 1)
    dp = dijkstra(n, graph, P)
    dq = dijkstra(n, graph, Q)
    
    # Case 1: One person visits P and Q
    S1 = d1[P] + dp[Q] + d1[Q]
    if S1 <= T:
        print(T)
        return
    
    # Case 3: Split at some city A
    max_together = -1
    for A in range(1, n+1):
        a_time = 2 * d1[A]
        p_time = 2 * dp[A]
        q_time = 2 * dq[A]
        current_max = max(p_time, q_time)
        total_time = a_time + current_max
        if total_time <= T:
            candidate = T - current_max
            if candidate > max_together:
                max_together = candidate
    
    print(max_together if max_together != -1 else -1)

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