시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 300 | 60 | 56 | 24.561% |
울산에는 $1$번부터 $N$번까지 번호가 붙은 $N$개의 교차로가 있고, 교차로와 교차로를 잇는 $M$개의 도로가 있다. 각 도로는 일방통행이며, 도로를 따라 이동하는 데 걸리는 시간이 정해져 있다.
윤이는 매일 현대모비스의 자율주행 시스템을 탑재한 차를 타고 집에서 회사로 출근한다. 윤이의 집은 $S$번 교차로에, 회사는 $T$번 교차로에 있다. 현대모비스의 자율주행 시스템은 항상 집에서 회사까지 최단 시간이 걸리는 주행 경로를 이용한다.
윤이는 얼마 전 울산에 새로운 도로 두 개가 건설될 것이라는 계획을 들었다. 윤이는 앞으로 회사에 더 빠르게 출근할 수 있을 거라는 기대감에 부풀어 있다. 하지만 윤이는 새 도로가 어떤 교차로를 잇는지와, 새 도로를 따라 이동하는 데 걸리는 시간이 얼마인지에 대한 내용을 듣지는 못했다. 따라서 윤이는 $Q$개의 도로 건설 시나리오를 가정하고, 각 상황에서 윤이의 자율주행차가 어떤 경로를 따라 주행할지 계산해 보기로 했다.
윤이가 가정한 $Q$개의 도로 건설 시나리오 각각에 대해, 윤이가 현대모비스 자율주행 시스템을 이용하여 집에서 회사로 출근하는 데 걸리는 시간을 구하시오.
첫 번째 줄에 교차로의 수 $N$, 기존 도로의 수 $M$, 집의 교차로 번호 $S$, 회사의 교차로 번호 $T$가 공백으로 구분되어 주어진다. ($2\leq N\leq 300$; $0\leq M\leq 3\ 000$; $1\leq S,T\leq N$; $S\neq T$)
이후 $M$개의 줄에 기존 도로에 대한 정보를 나타내는 정수 $u$, $v$, $w$가 공백으로 구분되어 주어진다. 시작 교차로가 $u$번, 도착 교차로가 $v$번이고 이동하는 데 $w$의 시간이 걸리는 일방통행 도로를 나타낸다. ($1\leq u,v\leq N$; $1\leq w\leq 10^6$)
그 다음 줄에 도로 건설 시나리오의 수 $Q$가 주어진다. ($1\leq Q\leq 100\ 000$)
이후 $Q$개의 줄에 새로 건설될 두 개의 도로에 대한 정보를 나타내는 정수 $a_1$, $b_1$, $c_1$, $a_2$, $b_2$, $c_2$가 공백으로 구분되어 주어진다. 시작 교차로가 $a_1$번, 도착 교차로가 $b_1$번이고 이동하는 데 $c_1$의 시간이 걸리는 일방통행 도로와, 시작 교차로가 $a_2$번, 도착 교차로가 $b_2$번이고 이동하는 데 $c_2$의 시간이 걸리는 일방통행 도로를 새롭게 건설하는 시나리오를 나타낸다. ($1\leq a_1,b_1,a_2,b_2\leq N$; $1\le c_1,c_2\le 10^6$)
같은 교차로 쌍을 잇는 도로가 여러 개 주어질 수 있으며, 시작 교차로와 도착 교차로가 동일한 도로가 주어질 수 있다.
각 도로 건설 시나리오에 대해, 윤이가 집에서 회사로 출근하는 데 걸리는 시간을 $Q$개의 줄에 걸쳐 출력한다. 만약 어떤 시나리오에서 집에서 회사로 출근하는 것이 불가능하다면, 해당 줄에는 대신 $-1$을 출력한다.
5 4 1 5 1 2 3 2 3 3 1 3 5 3 5 2 4 1 4 2 4 5 3 1 4 5 4 5 4 2 5 3 3 5 1 3 1 1 5 3 1
5 7 6 7