레이팅 미적용베시와 여동생 엘시는 헛간에서 가장 좋아하는 목초지까지 이동하려 하는데, 정확히 같은 시각에 출발해서 정확히 같은 시각에 도착하고 싶어 한다.
농장은 1..N번으로 번호가 매겨진 N개의 목초지로 이루어져 있으며 (1 <= N <= 100), 목초지 1에 헛간이 있고 목초지 N이 가장 좋아하는 목초지이다. 농장은 언덕 비탈에 있어서 X < Y이면 목초지 X가 목초지 Y보다 높은 곳에 있다. M개의 길이 목초지 쌍들을 연결하는데, 각 길은 내리막 방향으로만 다닐 수 있다. 각 목초지 쌍은 최대 하나의 길로만 연결된다.
같은 길이라도 베시와 엘시가 지나가는 데 걸리는 시간은 서로 다를 수 있다. 둘은 길 위를 이동할 때만 시간을 소비하며, 어디에서도 기다리지 않는다. 둘이 정확히 같은 순간에 가장 좋아하는 목초지에 도착하기 위해 필요한 최소 시간을 구하시오.
첫째 줄에 N과 M이 공백으로 구분되어 주어진다.
다음 M개의 줄 각각에는 길 하나를 나타내는 네 정수 A B C D가 주어진다. A와 B는 (A < B) 길이 연결하는 두 목초지이고, C는 베시가 걸리는 시간, D는 엘시가 걸리는 시간이다. C와 D는 모두 1..100 범위이다.
둘이 가장 좋아하는 목초지에 같은 순간에 도착하기 위해 필요한 최소 시간을 나타내는 정수 하나를 출력한다. 이것이 불가능하면 IMPOSSIBLE을 출력한다.
meeting.in · 출력을 쓸 파일 meeting.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 > Silver