레이팅 미적용농부 존은 베시에게 자신의 가장 좋은 밭 중 하나를 마음껏 풀을 뜯도록 내주었다. 이 밭은 N개의 풀밭 구역(1 <= N <= 1000)으로 덮여 있으며, 각 구역의 품질 값은 서로 다르다. 베시가 품질 Q의 풀을 먹으면 Q만큼의 에너지를 얻는다. 각 구역은 양방향 길을 통해 최대 10개의 이웃 구역과 연결되어 있으며, 인접한 구역 사이를 이동하는 데는 E만큼의 에너지가 든다(1 <= E <= 1,000,000). 베시는 원하는 어느 구역에서든 풀 뜯기를 시작할 수 있다.
베시는 입맛이 까다롭다. 일단 어떤 품질의 풀을 먹고 나면, 그 품질 이하의 풀은 다시는 먹지 않는다. 다만 풀을 먹지 않고 구역을 지나가는 것은 상관하지 않는다. 베시가 모을 수 있는 에너지의 최댓값을 구하시오.
첫째 줄에 N과 E가 주어진다. 나머지 N개의 줄에는 각각 한 구역을 나타내는 두 정수 Q와 D가 주어지는데, 이는 구역의 품질(1...1,000,000)과 이웃의 수를 의미하며, 그 뒤로 D개의 이웃 번호가 이어진다.
베시가 모을 수 있는 에너지의 최댓값을 출력한다.
buffet.in · 출력을 쓸 파일 buffet.out5 2
4 1 2
1 3 1 3 4
6 2 2 5
5 2 2 5
2 2 3 47Output details: Bessie starts at patch 4 (gain 5), walks to 5 (-2), walks to 3 (-2), eats at 3 (gain 6); total 7.
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > US Open > Silver