레이팅 미적용긴 하루가 끝나고 소들이 피곤하고 배고픈 상태로 헛간으로 돌아가고 있다.
농장은 \(N\)개의 목초지 (\(2 \leq N \leq 50,000\))로 이루어져 있으며, 편의상 \(1 \dots N\)번으로 번호가 매겨져 있다. 소들은 모두 목초지 \(N\)에 있는 헛간으로 가고 싶어한다. 나머지 \(N-1\)개의 목초지 각각에는 소가 한 마리씩 있다. 소들은 \(M\)개의 무향 오솔길 (\(1 \leq M \leq 100,000\))을 통해 목초지 사이를 이동할 수 있다. \(i\)번째 오솔길은 목초지 쌍 \(a_i\)와 \(b_i\)를 연결하며, 지나가는 데 시간 \(t_i\)가 걸린다. 모든 소는 오솔길들을 통해 헛간에 도달할 수 있다.
배가 고픈 소들은 집으로 가는 길에 음식을 먹으러 들를까 생각하고 있다. 마침 \(K\)개의 목초지에 맛있는 건초 더미가 있으며 (\(1 \leq K \leq N\)), \(i\)번째 건초 더미의 맛있음 값은 \(y_i\)이다. 각 소는 헛간으로 가는 길에 건초 더미 하나에 들를 의향이 있는데, 이로 인해 경로에 추가되는 시간이 방문하는 건초 더미의 맛있음 값 이하일 때에만 들른다. 소는 식사 목적으로는 "공식적으로" 최대 하나의 건초 더미만 방문한다는 점에 유의하자. 다만 경로가 건초 더미가 있는 다른 목초지를 지나가는 것은 상관없으며, 그 건초 더미들은 그냥 무시한다.
출제자: Dhruv Rohatgi
출제자: Dhruv Rohatgi
첫째 줄에 공백으로 구분된 세 정수 \(N\), \(M\), \(K\)가 주어진다. 다음 \(M\)개의 줄에는 각각 세 정수 \(a_i\), \(b_i\), \(t_i\)가 주어지며, 이는 목초지 \(a_i\)와 \(b_i\) 사이에 지나가는 데 시간 \(t_i\)가 걸리는 오솔길이 있음을 나타낸다 (\(a_i\)와 \(b_i\)는 서로 다르고, \(t_i\)는 \(10^4\) 이하의 양의 정수이다).
다음 \(K\)개의 줄에는 각각 건초 더미 하나를 나타내는 두 정수, 즉 건초 더미가 있는 목초지의 번호와 맛있음 값 (\(10^9\) 이하의 양의 정수)이 주어진다. 같은 목초지에 여러 개의 건초 더미가 있을 수 있다.
출력은 \(N-1\)개의 줄로 이루어진다. \(i\)번째 줄에는 목초지 \(i\)에 있는 소가 헛간으로 가는 길에 건초 더미에 들러 식사할 수 있으면 정수 \(1\)을, 그렇지 않으면 \(0\)을 출력한다.
dining.in · 출력을 쓸 파일 dining.out4 5 1
1 4 10
2 1 20
4 2 3
2 3 5
4 3 2
2 71
1
1In this example, the cow in pasture 3 should stop for a meal, since her route would only
increase by 6 (from 2 to 8), and this increase is at most the yumminess 7 of the
haybale. The cow in pasture 2 should obviously eat the hay in pasture 2, since
this causes no change in her optimal route. The cow in pasture 1 is an interesting
case, as it may first appear that her optimal route (length 10) would increase too
much to justify stopping for the hay. However, she actually does have a route that
makes stopping at the hay beneficial: move to pasture 4, then to pasture 2 (eating the hay),
then back to pasture 4.
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > December > Gold