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