結果

問題 No.807 umg tours
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:02:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,139 bytes
コンパイル時間 255 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 155,008 KB
最終ジャッジ日時 2025-04-09 21:05:24
合計ジャッジ時間 12,867 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import heapq

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N, M = int(data[idx]), int(data[idx+1])
    idx += 2
    edges = [[] for _ in range(N+1)]
    for _ in range(M):
        a = int(data[idx])
        b = int(data[idx+1])
        c = int(data[idx+2])
        idx += 3
        edges[a].append((b, c))
        edges[b].append((a, c))
    
    # Dijkstra to find d1 and parent/max_e
    INF = 1 << 60
    d1 = [INF] * (N+1)
    max_e = [0] * (N+1)
    parent = [-1] * (N+1)
    visited = [False] * (N+1)
    heap = []
    d1[1] = 0
    heapq.heappush(heap, (0, 1, -1, 0))  # (distance, node, parent, max_edge)
    
    while heap:
        dist, u, p, me = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        parent[u] = p
        max_e[u] = me
        for v, c in edges[u]:
            if not visited[v] and d1[v] > dist + c:
                d1[v] = dist + c
                new_me = max(me, c)
                heapq.heappush(heap, (d1[v], v, u, new_me))
            elif not visited[v] and d1[v] == dist + c:
                new_me = max(me, c)
                if new_me < max_e[v]:  # ensure the maximum edge is tracked
                    max_e[v] = new_me
                    parent[v] = u
    
    minimal_s = [INF] * (N+1)
    
    for _ in range(M):
        a = int(data[idx-3*M+3*_])
        b = int(data[idx-3*M+3*_+1])
        c_val = int(data[idx-3*M+3*_+2])
        u = a
        v = b
        s = d1[u] + d1[v]
        # Process u
        current = u
        while current != -1:
            if minimal_s[current] <= s:
                break
            minimal_s[current] = s
            current = parent[current]
        # Process v
        current = v
        while current != -1:
            if minimal_s[current] <= s:
                break
            minimal_s[current] = s
            current = parent[current]
    
    for i in range(1, N+1):
        default = 2 * d1[i] - max_e[i]
        res = min(default, minimal_s[i] if minimal_s[i] != INF else default)
        print(res)
    
if __name__ == "__main__":
    main()
0