31268번 - 물자 조달 서브태스크

문제

현재 A국과 B국 두 나라는 서로 전쟁 중이다. A국의 운전병 해찬이는 조국의 승리를 위해 출발 부대에서 도착 부대로 물자를 조달하는 임무를 맡았다.

A국에는 1ドル$부터 $N$까지 번호가 매겨진 $N$개의 부대가 존재하며 각 부대는 도로로 연결되어 있다. 또한, 각 도로를 지나갈 때는 일정한 시간이 소요된다.

각 부대들은 보안을 위해 들어오는 차량을 검문하며, 이때 검문시간 $t_i$가 소요된다. 다만 출발 부대와 도착 부대에는 미리 공문이 내려가 있기 때문에 검문시간이 소요되지 않는다.

B국은 A국의 각 부대를 목표로 삼아 습격하며 이때 습격받은 부대는 보안이 강화되어 검문시간이 증가한다. 또한 B국은 한 번 공격 목표가 다른 부대로 바뀌면 이후 이전에 목표로 삼았던 부대들은 다시 공격하지 않는다.

다음과 같은 $Q$개의 쿼리가 주어질 때 해찬이를 도와 A국의 승리를 도와주자.

• 1ドル$ $r$ $c$: B국이 $r$번 부대를 공격하여 $r$번 부대의 검문시간이 $c$만큼 증가한다.
• 2ドル$ $a$ $b$: $a$번 부대에서 $b$번 부대로 가는 최소 시간을 출력한다. 도달할 수 없다면 -1을 출력한다.

입력

첫 번째 줄에 부대의 수 $N,ドル 도로의 수 $M,ドル 쿼리의 수 $Q$가 공백으로 구분되어 주어진다.

두 번째 줄에 각 부대의 검문시간을 의미하는 $N$개의 정수 $t_1, \cdots, t_N$이 공백으로 구분되어 주어진다.

이후 $M$개의 줄에 걸쳐 $u,v,w$가 공백으로 구분되어 주어지며 이는 $u$번 부대에서 $v$번 부대로 가는데 $w$만큼의 시간이 걸리는 양방향 도로가 존재한다는 뜻이다.

이후 $Q$개의 줄에 걸쳐 다음과 같은 두 가지 종류의 쿼리가 한 줄에 하나씩 주어진다.

• 1ドル$ $r$ $c$: B국이 $r$번 부대를 공격하여 $r$번 부대의 검문시간이 $c$만큼 증가한다.
• 2ドル$ $a$ $b$: $a$번 부대에서 $b$번 부대로 가는 최소 시간을 출력한다. 도달할 수 없다면 -1을 출력한다.

출력

주어진 2번 쿼리의 출력값을 한 줄에 하나씩 출력한다.

제한

• 2ドル \le N \le 200$
• 1ドル \le M \le \frac{N(N-1)}{2}$
• 1ドル \le Q \le 10^6$
• 1ドル \le t_i \le 10^4$
• 1ドル \le u,v \le N$; $u \neq v$
• 1ドル \le w \le 10^7$
• 1ドル \le r \le N$
• 1ドル \le c \le 100$
• 1ドル \le a,b \le N$; $a \neq b$
• 모든 입력은 정수이다.

서브태스크

힌트