Meeting Time (Bronze)
브론즈 II의견: 0
Bessie and her sister Elsie want to travel from the barn to their favorite field, leaving at exactly the same time and arriving at exactly the same time.
The farm is a collection of N fields (1 <= N <= 16) numbered 1..N, where field 1 contains the barn and field N is the favorite field. The farm is on a hillside, with field X higher than field Y if X < Y. M paths connect pairs of fields, but each path can only be followed downhill (a path between fields 5 and 8 can be followed 5 -> 8 but not 8 -> 5). Each pair of fields is connected by at most one path.
It may take Bessie and Elsie different amounts of time to follow a path. They only consume time while traveling on paths, never waiting anywhere. Please help determine the shortest amount of time they must take to reach their favorite field at exactly the same moment.
Line 1: N and M, separated by a space.
Each of the next M lines describes a path with four integers A B C D, where A and B (A < B) are the fields connected by the path, C is the time for Bessie to follow it, and D is the time for Elsie. Both C and D are in the range 1..1000.
A single integer giving the minimum time required for Bessie and Elsie to reach their favorite field and arrive at the same moment. If this is impossible (or if either cannot reach the field at all), output the word IMPOSSIBLE.
meeting.inmeeting.out3 3
1 3 1 2
1 2 1 2
2 3 1 22Output details: If Bessie takes 1->2->3 and Elsie takes 1->3 they arrive at the same time.
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > January > Bronze
평가 및 의견
Meeting Time (Bronze)
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Meeting Time (Bronze)