提出 #58203631

---

ソースコード 拡げる

import sys
from collections import deque
#sys.stdin = open('in.txt', 'r')
#sys.stdout = open('out.txt', 'w')
read = sys.stdin.readline
write = sys.stdout.write
def solve_graph(N, M, edges):
    adj = [[] for _ in range(N + 1)]
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, -w))

    x = [None] * (N + 1)
    visited = [False] * (N + 1)

    def bfs(start):
        queue = deque([start])
        x[start] = 0 
        visited[start] = True
        component = []

        while queue:
            node = queue.popleft()
            current_value = x[node]
            component.append(node)

            for neighbor, weight in adj[node]:
                if not visited[neighbor]:
                    x[neighbor] = current_value + weight
                    visited[neighbor] = True
                    queue.append(neighbor)

        component_values = [x[node] for node in component]
        min_value = min(component_values)
        max_value = max(component_values)

        limit = 10**18
        if min_value < -limit or max_value > limit:
            shift = max(-min_value - limit, max_value - limit)
            for node in component:
                x[node] += shift

    for i in range(1, N + 1):
        if not visited[i]:
            bfs(i)

    return x[1:]

n, m = map(int, read().split())
edges = []
for i in range(m):
    u,v,w = map(int, read().split())
    edges.append((u,v,w))
write(' '.join(map(str, solve_graph(n,m,edges)))+'\n')

提出情報

ジャッジ結果