Dynamic Shortest Path
해결한 사람
0
명
정답률
0.00
%
시간 제한
10000
ms
메모리 제한
489
MB
문제 설명
n개의 정점과 m개의 간선으로 이루어진 가중치가 있는 유향 그래프가 주어진다. 다음 두 유형의 쿼리 q개에 답해야 한다:
- 1 v — 정점 1에서 정점 v까지의 최단 경로 길이를 구한다.
- 2 c l1 l2 ... lc — 인덱스가 l1, l2, ..., lc인 간선들의 가중치에 1을 더한다.
입력 형식
입력 데이터의 첫 번째 줄에는 정수 n, m, q (1 ≤ n, m ≤ 105, 1 ≤ q ≤ 2000)가 주어진다. 각각 그래프의 정점 수와 간선 수, 요청 수를 나타낸다.
이어지는 입력 데이터의 m개 줄에는 간선에 대한 설명이 주어진다. 그중 i-th번째 줄에는 인덱스가 i인 간선에 대한 설명, 즉 세 정수 ai, bi, ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 109)가 주어진다. 각각 간선의 시작점과 끝점, 초기 가중치를 나타낸다.
이어지는 입력 데이터의 q개 줄에는 위에서 설명한 형식으로 간선에 대한 설명이 주어진다 (1 ≤ v ≤ n, 1 ≤ lj ≤ m). 하나의 쿼리 안에서 모든 lj가 서로 다름이 보장된다. 또한 두 번째 유형의 모든 요청에 포함된 간선 수의 합은 106을 넘지 않음이 보장된다.
출력 형식
첫 번째 유형의 각 쿼리마다 1에서 v까지의 최단 경로 길이를 별도의 줄에 출력한다. 그러한 경로가 존재하지 않으면 -1을 출력한다.
예제
예제 입력 1
3 2 9
1 2 0
2 3 0
2 1 2
1 3
1 2
2 1 1
1 3
1 2
2 2 1 2
1 3
1 2
예제 출력 1
1
0
2
1
4
2
예제 입력 2
5 4 9
2 3 1
2 4 1
3 4 1
1 2 0
1 5
1 4
2 1 2
2 1 2
1 4
2 2 1 3
1 4
2 1 4
1 4
예제 출력 2
-1
1
2
3
4
참고
첫 번째 예제에서 그래프가 변화하는 과정은 다음과 같다:
두 번째 예제에서 그래프가 변화하는 과정은 다음과 같다:
