Bessie's Birthday Buffet
골드 I의견: 0
Farmer John has given Bessie free reign over one of his best fields to eat grass. The field is covered in N patches of grass (1 <= N <= 1000), each with a distinct quality value. If Bessie eats grass of quality Q, she gains Q units of energy. Each patch is connected to up to 10 neighboring patches via bi-directional paths, and it takes Bessie E units of energy to move between adjacent patches (1 <= E <= 1,000,000). Bessie can start grazing in any patch she wishes.
Bessie is picky: once she eats grass of a certain quality, she'll never eat grass at or below that quality level again. She is still happy to walk through patches without eating their grass. Please help determine the maximum amount of energy Bessie can accumulate.
Line 1: N and E. Each of the remaining N lines describes a patch with two integers Q and D giving the quality of the patch (1...1,000,000) and its number of neighbors, followed by the D neighbor indices.
The maximum amount of energy Bessie can accumulate.
buffet.inbuffet.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
평가 및 의견
Bessie's Birthday Buffet
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Bessie's Birthday Buffet