Informatica Online Judge

  교준이의 심부름꾼, 민제의 고충 ("AND" Ver.) #4 [2266 / 08DA]

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


The Champion of this Problem (C++) : gs17018 - 463ms / 1992byte
My Best Submission (C++) : N/A

[35th 윤교준]

Background

민제는 지하철 하나 없는 대한민국의 유일한 도시 청주에서 살고 있다.
청주에는 1부터 N까지 번호가 붙은 N개의 군(郡)이 M개의 양방향 도로로 연결되어 있는 형태다.
$i$번째 도로는 $A_i$번 군과 $B_i$번 군을 비용 $C_i$에 양방향으로 오갈 수 있도록 연결한다.

$u$번 군에서 $v$번 군으로 가는데 필요한 비용은, 이동 경로를 { $e_1$ → $e_2$ → ... → $e_k$ }라고 하였을 때, $C_{e_1} ∧ C_{e_2} ∧ ... ∧ C_{e_k}$다.
여기서 $e_i$는 $i$번째로 사용한 도로의 index를 의미하며, ∧는 논리곱을 나타내는 기호다.

청주는 전기조차 제대로 들어오지 않는 낙후된 도시기에, 도로에 있는 가로등은 자주 고장이 난다.
민제는 졸보라서, 가로등이 고장난 도로는 무서워서 절대 지나갈 수 없다.
게다가 민제는 가난한 구두쇠라, 어떤 군에서 다른 군으로 이동할 일이 생기면 항상 최소 비용 경로를 따라 이동한다.

8살때부터 민제는 교준이의 심부름꾼이었다.
교준이가 민제에게 "$u$번 군에서 빵을 사서 $v$번 군으로 와라."라고 시키면, 정말로 민제는 순순히 $u$번 군에서 빵을 사서 $v$번 군에 있는 교준이에게 빵을 배달해준다.
허나 민제는 "1+9+10=19"라고 말할 정도로 산수를 못하는 바보다.
민제를 위하여 $u$번 군에서 $v$번 군으로 갈 때 필요한 최소 비용을 계산해주자!

Input

첫 번째 줄에는 청주의 군의 개수를 나타내는 자연수 $N$과 도로의 개수를 나타내는 자연수 $M$, 쿼리의 개수를 나타내는 자연수 $Q$가 사이에 공백을 두고 주어진다.
두 번째 줄부터 $M$개의 줄에 걸쳐 $M$개의 도로에 관한 정보가 주어진다.
$(i+1)$번째 줄에는 세 정수 $A_i$, $B_i$, $C_i$가 사이에 공백을 두고 주어진다($1 ≤ i ≤ M$).
$(M+2)$번째 줄에는 각 도로의 가로등의 상태를 나타내는 정수 $M$개가 사이에 공백을 두고 주어진다.
$(M+2)$번째 줄의 $i$번째 정수가 0이면 $i$번째 도로의 가로등이 고장 났음을, 1이면 정상적으로 작동함을 의미한다($1 ≤ i ≤ M$).
$(M+3)$번째 줄부터 $Q$개의 줄에 걸쳐 $Q$개의 쿼리에 관한 정보가 순서대로 주어진다.
$(i+M+2)$번째 줄에는 $i$번째 쿼리의 정보를 담고 있으며, 그 의미는 다음과 같다:
"1 $i$" : $i$번째 도로의 가로등의 상태가 변한다($1 ≤ i ≤ M$). (고장났으면 고쳐지고, 정상적으로 작동중이면 고장난다.)
"2 $u$ $v$" : 교준이가 민제에게 "$u$번 군에서 빵을 사서 $v$번 군으로 와라."라고 심부름을 시킨 상황이다. $u$번 군에서 $v$번 군으로 가는 데 필요한 최소 비용을 하나의 줄에 출력한다($1 ≤ u ≤ N$, $1 ≤ v ≤ N$, $u ≠ v$).

[입력값의 제약조건]
모든 입력 데이터는 아래의 조건을 모두 만족한다.
$1 ≤ N ≤ 2 × 10^5$
$1 ≤ M ≤ 4 × 10^5$
$1 ≤ Q ≤ 4 × 10^5$
$1 ≤ A_i ≤ N$ ($1 ≤ i ≤ M$)
$1 ≤ B_i ≤ N$ ($1 ≤ i ≤ M$)
$0 ≤ C_i < 2^{30}$ ($1 ≤ i ≤ M$)
적어도 한 개 이상의 Type 2 쿼리가 존재한다.

Output

Type 2인 쿼리에 대하여, $u$번 군에서 $v$번 군으로 가는 데 필요한 최소 비용을 출력한다.
만일 $u$번 군에서 $v$번 군으로 이동할 수 없는 경우, "-1"(큰따옴표 제외)를 출력한다.

IO Example

입력
5 7 12
1 2 15
2 3 13
1 3 14
4 5 11
4 5 14
4 5 13
4 4 7
1 0 0 1 0 0 1
2 1 2
2 4 5
2 1 5
1 3
2 2 3
1 2
2 1 2
1 5
1 6
2 4 5
1 5
2 4 5

출력
15
3
-1
14
12
0
1

보충 설명
위의 입출력 예제는 Subtask 2.와 Subtask 4.의 입출력 데이터에만 존재한다.

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