Informatica Online Judge

  명진이의 여행 [2365 / 093D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 3   Total Tried : 4


The Champion of this Problem (C++) : gs18081 - ms / 2427byte
My Best Submission (C++) : N/A

[36th 이민준 (gs18081)]
Writer ID : [gs18081]

Background

명진이는 여행하는 것을 좋아한다. 명진이는 다익스트라 알고리즘이 잘 돌아가는 방향 그래프를 좋아하지만,이번에 명진이는 무방향 그래프를 여행할 것이다.

명진이가 여행하는 그래프에는 한 가지 특징이 있는데, 바로 간선의 가중치에 중복이 없다는 것이다. 즉, 가중치가 같은 간선은 없다.

명진이는 1번 정점에서 여행을 시작할 것인데, 명진이가 각 정점을 목표로 하고 여행을 떠날 때 명진이가 지키는 하나의 원칙이 있다. 그것은 명진이가 그 정점을 가기 위해 필요한 경로에 포함되는 간선의 가중치의 최대값을 최소화하면서 떠나려고 하는 것이다. 만약 그러한 경로가 여러 가지라면, 그 다음으로 큰 값이 더 작은 경로를, 그래도 같다면 또 그 다음으로 큰 값이 작은 경로를 선택한다.

명진이가 여행을 떠나는 그래프의 정점들에는 멋진 예술작품이 있는데, 명진이는 이러한 예술작품의 아름다움을 숫자로 매겨놓았다.

또한, 시간이 지남에 따라서 예술작품들이 교체되므로, 그래프에 있는 정점들의 예술작품의 아름다움이 변할 수도 있다.

명진이는 문득 궁금해졌다. 어떠한 정점을 반드시 지나서 가게 되는 정점들에 있는 예술작품의 아름다움의 합은 얼마인지 말이다. 명진이는 방향 그래프 관련 문제에 대해서는 전문가이지만, 아직 무방향 그래프에 대해서는 익숙치 않으므로 여러분에게 이 문제에 대한 답을 구하도록 물어보고자 한다. 명진이의 질문에 답해주자!

Input

1번째 줄에는 명진이가 여행할 그래프의 정점 개수 N과 간선의 개수 M, 그리고 질문의 개수 Q가 주어진다.
(1<=N<=100000, 1<=M<=300000 , 1<=Q<=200000)
다음 N개의 줄에는 정점의 초기 예술작품의 아름다움 b가 주어진다.
(1<=b<=1000)
그 다음 M개의 줄에는 간선이 연결하고 있는 두 정점 a, b와 가중치 c가 주어진다. 가중치는 중복되지 않음이 보장된다.
(1<=a , b <= N , 1<=c<=10^9)
다음 Q개의 줄에는 질의가 주어지는데, 질의의 종류는 총 2가지이다.

0 으로 시작하는 질의는 정점의 예술작품의 아름다움이 변하는 질의이다.
그 뒤에는 정점의 번호 n, 변한 아름다움 b 가 순서대로 주어진다.
(1<=n<=N , 1<=b<=1000)
1로 시작하는 질의는 명진이가 여러분에게 어떠한 정점을 지나서 가야 하는 정점들의 예술작품의 아름다움의 합을 구하도록 하는 질의의다.
그 뒤에는 정점의 번호가 주어진다.
(1<=n<=N)

Output

1로 시작하는 질의에 대해서, 순서대로 아름다움의 합에 대해서 출력한다. 1로 시작하는 질의가 하나 이상 있음이 보장된다.

IO Example

입력1
4 5 5
1 2 3 4
1 2 8
1 3 1
2 3 4
2 4 2
3 4 6
1 3
1 4
0 1 10
1 1
1 2

출력1
9
4
19
6


* 설명 :



1번 정점으로 가는 경로 : 1
2번 정점으로 가는 경로 : 1 -> 3 -> 2
3번 정점으로 가는 경로 : 1 -> 3
4번 정점으로 가는 경로 : 1 -> 3 -> 2 -> 4
이므로 3을 지나가는 정점은 2,3,4 이므로 답은 9이고
4를 지나가는 정점은 4뿐이고,
1의 아름다움을 10으로 바꾼 뒤에 1을 지나가는 정점은 전부이므로 19이고,
2를 지나가는 정점은 2, 4 이므로 6이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]