結果

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

ソースコード

diff # 

import heapq

def dijkstra(n, adj, start):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        current_dist, u = heapq.heappop(heap)
        if current_dist > dist[u]:
            continue
        for v, c in adj[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().split()
    ptr = 0
    N = int(input[ptr]); ptr +=1
    M = int(input[ptr]); ptr +=1
    P = int(input[ptr]); ptr +=1
    Q = int(input[ptr]); ptr +=1
    T = int(input[ptr]); ptr +=1
    
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        a = int(input[ptr]); ptr +=1
        b = int(input[ptr]); ptr +=1
        c = int(input[ptr]); ptr +=1
        adj[a].append((b, c))
        adj[b].append((a, c))
    
    # Calculate shortest paths
    dist_1 = dijkstra(N, adj, 1)
    dist_P = dijkstra(N, adj, P)
    dist_Q = dijkstra(N, adj, Q)
    
    # Check if any cities are unreachable (though problem statement says all are reachable)
    max_shared = -1
    
    # Check scenario 1: 1 -> P -> Q -> 1
    time_case1 = dist_1[P] + dist_P[Q] + dist_Q[1]
    if time_case1 <= T:
        max_shared = T
    
    # Check scenario 2: 1 -> Q -> P -> 1
    time_case2 = dist_1[Q] + dist_Q[P] + dist_P[1]
    if time_case2 <= T:
        max_shared = max(max_shared, T)
    
    # Check scenario 3: Split at city A
    max_candidate = -1
    for A in range(1, N+1):
        d1A = dist_1[A]
        dPA = dist_P[A]
        dQA = dist_Q[A]
        if d1A == float('inf') or dPA == float('inf') or dQA == float('inf'):
            continue  # Skip unreachable cities
        max_val = max(2 * dPA, 2 * dQA)
        time_total = 2 * d1A + max_val
        if time_total <= T:
            current_shared = T - max_val
            if current_shared > max_candidate:
                max_candidate = current_shared
    
    # Update max_shared with the best candidate from scenario 3
    if max_candidate != -1:
        max_shared = max(max_shared, max_candidate)
    
    # Output the result
    print(max_shared if max_shared != -1 else -1)

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