結果

問題 No.848 なかよし旅行
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:52:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,986 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 116,264 KB
最終ジャッジ日時 2025-03-31 17:52:52
合計ジャッジ時間 5,895 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq

def dijkstra(n, adj, start):
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, u = heapq.heappop(heap)
        if cost > 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()
    idx = 0
    N, M, P, Q, T = map(int, input[idx:idx+5])
    idx +=5
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input[idx:idx+3])
        idx +=3
        adj[a].append((b, c))
        adj[b].append((a, c))
    
    # Dijkstra from 1, P, Q
    d1 = dijkstra(N, adj, 1)
    dp = dijkstra(N, adj, P)
    dq = dijkstra(N, adj, Q)
    
    max_time = -1
    
    # Case A: 1 -> P -> Q ->1
    time_caseA = d1[P] + dp[Q] + d1[Q]
    if time_caseA <= T:
        max_time = max(max_time, T)
    
    # Case B: 1 -> Q -> P ->1 (unnecessary as it's same as A for undirected graph)
    
    # Case C: for all possible X
    best_caseC = -1
    for X in range(1, N+1):
        if d1[X] == float('inf'):
            continue
        dX_p = dp[X]  # P to X is same as X to P in undirected graph
        dX_q = dq[X]  # Q to X is same as X to Q
        time_separate = max(2 * dX_p, 2 * dX_q)
        total_time = 2 * d1[X] + time_separate
        if total_time > T:
            continue
        candidate = T - time_separate
        if candidate > best_caseC:
            best_caseC = candidate
    if best_caseC != -1:
        max_time = max(max_time, best_caseC)
    
    # Case D: separate travel
    time_p = 2 * d1[P]
    time_q = 2 * d1[Q]
    max_separate = max(time_p, time_q)
    if max_separate <= T:
        candidate = T - max_separate
        max_time = max(max_time, candidate)
    
    print(max_time if max_time != -1 else -1)

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