시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 2074 | 302 | 166 | 13.685% |
엔지니어의 행복도는 퇴근 후 집에 도착하는 시각이 늦을수록 낮아진다는 것이 증명되었다.
조이의 대표 레드는 엔지니어의 행복도를 최대한 높여야 할 의무가 있기 때문에, 신중하게 퇴근 시간을 조정하기로 하였다.
하지만 퇴근 시간을 조정하려면 먼저 엔지니어들이 집에 도착하는 시간을 알아야만 했다.
이 문제를 미카에게 맡기려고 했지만, 6시가 넘어 미카는 이미 퇴근해버렸기 때문에 레드는 고민에 빠지고 말았다.
레드를 도와 레드와 조이 엔지니어 모두의 행복도를 높여보도록 하자!
회사가 있는 서울은 N개의 지점으로 되어있다.
각 지점은 1번부터 N번의 번호를 가지고 있고, 회사는 1번 지점에 있다.
M개의 도로들은 서로 다른 지점을 연결하고 있으며, 임의의 지점에서 모든 지점으로 이동할 수 있다.
각각의 도로는 길이를 가지고 있으며, 거리 1을 이동하는 데 1분이 걸린다.
편의상 퇴근은 0분에 한다고 가정한다.
서울은 퇴근 시간에 도로가 막힌다.
퇴근 시간이 아닐 때에는 거리 1을 이동하는 데 1분이 걸리지만,
퇴근 시간이 겹칠 경우 혼잡한 도로는 거리 1을 이동하는 데 2분이 걸리게 된다. (물론 퇴근 시간에 막히지 않는 도로도 있다.)
만약 퇴근 시간이 10분부터 20분이고 어떤 도로에 진입한 순간이 15분이며, 도로의 길이는 10이라면 이 도로를 전부 통과하는 데 걸리는 시간은
총 12.5분이 된다.
첫째 줄에는 N, M과 퇴근 시간의 시작과 끝을 의미하는 S와 E가 정수로 주어진다. (2 ≤ N ≤ 5,000, 1 ≤ M ≤ 100,000, 0 ≤ S < E ≤ 1,000,000,000)
다음 M개의 줄에는 서로 다른 정수 A, B와 도로의 길이를 의미하는 L, 그리고 t1, t2가 주어진다. (1 ≤ A, B ≤ N, 1 ≤ L ≤ 1,000,000,000, t1, t2 = 0 또는 1)
t1, t2는 A,B 사이에 퇴근 시간에 도로가 정체되는지 여부이다.
퇴근할 때는 같은 길로는 2번 이상 이동하지 않는다. 사원들은 언제나 최대한 빨리 집에 가고 싶어하기 때문에 일부러 늦는 길을 선택하지 않는다. 또한 이동할 때 멈추지 않고 계속 이동한다.
모든 지점에 대해서 회사에서 출발했을 때 가장 늦게 도착하게 되는 지점까지의 도착 시각을 첫째 줄에 출력하라.
7 6 5 13 1 2 8 1 0 3 2 4 0 1 1 5 5 0 0 1 4 10 0 0 1 6 10 0 0 6 7 5 0 0
16
7 6 4 13 1 2 8 1 0 3 2 4 0 1 1 5 5 0 0 1 4 10 0 0 1 6 10 0 0 6 7 5 0 0
16.5
퇴근 시간이 없다면 7번에 도착하는 시각인 15분이 가장 늦게 된다.
하지만 3번까지 가는 경로가 정체가 되기 때문에 3번에 도착하는 시각이 16분으로 가장 늦게 된다.
합 16분