Problemas
사람들이 내비게이션의 편리함에 젖어 몇몇 도로만 드나들다 보니 교통체증이 심해지기 시작했다.
이에 따라 도로의 통행시간이 계속 바뀌는데, 기존 내비게이션의 알고리즘은 도로 정보를 바꿀 때마다
최적 경로를 탐색하는 시간이 오래 걸려서 도로의 통행시간 변동 속도를 따라가지 못하게 되었다.
큰 문제가 생기자 내비게이션 회사는 도로 정보가 바뀔 때 빨리 최단경로를 구해주는 소프트웨어를 새로 짜기 시작했는데,
우선 수요가 많은 강변북로 및 올림픽대로 구간만 모델링하여 최적 경로를 구하려고 한다.
한강 북쪽에 강변북로, 남쪽에 올림픽대로가 있으며 강변북로와 올림픽대로에 각각
강변북로에 있는 나들목의 코드는 가장 서쪽에 있는 것부터 순서대로 N[1], N[2], ..., N[N]이고,
올림픽대로에 있는 나들목의 코드는 서쪽부터 순서대로 S[1], S[2], ..., S[N]이다.
강변북로 N[i]번 나들목과 N[i+1]번 나들목을 이으며, 올림픽대로 S[i]번 나들목과 S[i+1]번 나들목을 잇는다.
한강에 있는 N[i]번 나들목과 S[i]번 나들목을 잇는다.
각 도로 및 다리는 양방향으로 이동 가능하며 한쪽 끝에서 다른쪽 끝까지 가는데 일정한 시간이 걸린다.
내비게이션 서버는 맨 처음에
이 정보를 토대로 내비게이션 서버는 수시로 운전자가 '여기에서 저기로 가는 가장 빠른 길을 알려주세요'라고 물을 때마다
재빨리 답을 구하여 보내야 한다. 도로의 통행 시간 변동과 운전자의 최단거리 계산 질문을 빠르게 처리하는 프로그램을 작성하여라.
Entrada
첫 번째 줄에 다리의 수
두 번째 줄에는 강변북로에 있는
세 번째 줄에는 올림픽대로에 있는
네 번째 줄에는 한강에 있는
다섯 번째 줄에는 추가 정보 또는 질문의 수
여섯 번째 줄부터
1 a b:a 번 나들목에서b 번 나들목까지 가는데 걸리는 최소 시간을 구해라.a 와b 는 서로 다르며,
강변북로x 번째 나들목은Nx꼴로, 올림픽대로x 번째 나들목은Sx꼴로 주어진다.2 a T: 강변북로a 번째 도로를 지나는데 걸리는 시간G_a 가T 로 바뀐다. (1 \le a \le N-1 ,1 \le T \le 1\,000\,000\,000 )3 b T: 올림픽대로b 번째 도로를 지나는데 걸리는 시간O_b 가T 로 바뀐다. (1 \le b \le N-1 ,1 \le T \le 1\,000\,000\,000 )4 c T: 한강에 있는c 번째 다리를 지나는데 걸리는 시간B_c 가T 로 바뀐다. (1 \le c \le N ,1 \le T \le 1\,000\,000\,000 )
1번 유형의 질문은 최소 한 번 이상 등장한다.
Salida
1번 유형의 질문에 대하여, 질문의 답을 한 줄에 하나씩 출력한다.
Subtarea
| # | Puntaje | Condición |
|---|---|---|
| #1 | 9 | |
| #2 | 18 | 2, 3번 유형 추가 정보가 등장하지 않는다. |
| #3 | 23 | 모든 2, 3번 유형 추가 정보에 대하여 |
| #4 | 24 | 모든 1번 유형 질문에 대하여 |
| #5 | 26 | 추가 제약조건은 없다. |
Ejemplo #1
7
1 2 1 1 1 2
1 1 1 3 3 1
10 9 7 12 11 8 10
6
1 N2 S4
4 6 2
1 N3 S5
3 3 8
2 4 2
1 N2 S4
10
8
14
Ejemplo #2
4
1 1000000000 1
1000000000 1 1000000000
1000000000 1 1 1000000000
1
1 N1 N4
5
Debes iniciar sesión para escribir código.