# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
832310 | daniel604 | Harbingers (CEOI09_harbingers) | Cpython 3 | 802 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
# vertex에 트리 저장
vertex = [{} for _ in range(N + 1)]
for _ in range(N - 1):
U, V, D = map(int, input().split())
vertex[U][V] = D
vertex[V][U] = D
# S[i], V[i]는 i 도시의 전령 정보
S, V = [0] * (N + 1), [0] * (N + 1)
for i in range(N - 1):
s, v = map(int, input().split())
S[i + 2], V[i + 2] = s, v
# DFS를 재귀함수를 통해 진행하자
# DFS의 마지막에 graph를 복귀시켜주면 된다.
# 방금 바꾼 그 하나만 복귀시키면 된다.
# 따로 저장해두고, 다시 불러오는 과정은 시간, 메모리 초과할 듯
# graph에 하나 추가하면 graph의 크기와 graph의 마지막 값 변경됨
# graph 크기는 lenght로 저장한다.
# dp[i] = min(-D[j] x V[i] + dp[j]) + S[i] + D[i] x V[i]
distance = [0] * (N + 1)
# child만 저장, (기울기, y절편) -> (-distance[i], dp[i])
graph, lenght = [0] * N, 0
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |