English · Original
Chinese · Translation
Formal · Original
You are given a weighted directed graph, consisting of _n_ vertices and _m_ edges. You should answer _q_ queries of two types:
* _1 v_ — find the length of shortest path from vertex 1 to vertex _v_.
* _2 c _l_1 _l_2 ... _l__c__ — add 1 to weights of edges with indices _l_1, _l_2, ..., _l__c_.
## Input
The first line of input data contains integers _n_, _m_, _q_ (1 ≤ _n_, _m_ ≤ 105, 1 ≤ _q_ ≤ 2000) — the number of vertices and edges in the graph, and the number of requests correspondingly.
Next _m_ lines of input data contain the descriptions of edges: _i_\-th of them contains description of edge with index _i_ — three integers _a__i_, _b__i_, _c__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_, 0 ≤ _c__i_ ≤ 109) — the beginning and the end of edge, and its initial weight correspondingly.
Next _q_ lines of input data contain the description of edges in the format described above (1 ≤ _v_ ≤ _n_, 1 ≤ _l__j_ ≤ _m_). It's guaranteed that inside single query all _l__j_ are distinct. Also, it's guaranteed that a total number of edges in all requests of the second type does not exceed 106.
## Output
For each query of first type print the length of the shortest path from 1 to _v_ in a separate line. Print _\-1_, if such path does not exists.
[samples]
## Note
<center>The description of changes of the graph in the first sample case:
The description of changes of the graph in the second sample case:
</center>
你被给定一个带权有向图，包含 #cf_span[n] 个顶点和 #cf_span[m] 条边。你需要回答 #cf_span[q] 个查询，分为两种类型：
输入的第一行包含整数 #cf_span[n], #cf_span[m], #cf_span[q] (#cf_span[1 ≤ n, m ≤ 10^5], #cf_span[1 ≤ q ≤ 2000]) —— 分别表示图中的顶点数、边数和查询数。
接下来的 #cf_span[m] 行描述了边：第 #cf_span[i] 行包含索引为 #cf_span[i] 的边的描述——三个整数 #cf_span[ai], #cf_span[bi], #cf_span[ci] (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[0 ≤ ci ≤ 10^9])，分别表示边的起点、终点及其初始权重。
接下来的 #cf_span[q] 行描述了查询，格式如上所述（#cf_span[1 ≤ v ≤ n], #cf_span[1 ≤ lj ≤ m]）。保证在单个查询中所有 #cf_span[lj] 互不相同。同时保证所有第二类查询中涉及的边总数不超过 #cf_span[10^6]。
对于每个第一类查询，请在单独一行中输出从 #cf_span[1] 到 #cf_span[v] 的最短路径长度。如果不存在这样的路径，请输出 _-1_。
第一个样例中图的变化描述：
第二个样例中图的变化描述：
## Input
输入的第一行包含整数 #cf_span[n], #cf_span[m], #cf_span[q] (#cf_span[1 ≤ n, m ≤ 10^5], #cf_span[1 ≤ q ≤ 2000]) —— 分别表示图中的顶点数、边数和查询数。接下来的 #cf_span[m] 行描述了边：第 #cf_span[i] 行包含索引为 #cf_span[i] 的边的描述——三个整数 #cf_span[ai], #cf_span[bi], #cf_span[ci] (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[0 ≤ ci ≤ 10^9])，分别表示边的起点、终点及其初始权重。接下来的 #cf_span[q] 行描述了查询，格式如上所述（#cf_span[1 ≤ v ≤ n], #cf_span[1 ≤ lj ≤ m]）。保证在单个查询中所有 #cf_span[lj] 互不相同。同时保证所有第二类查询中涉及的边总数不超过 #cf_span[10^6]。
## Output
对于每个第一类查询，请在单独一行中输出从 #cf_span[1] 到 #cf_span[v] 的最短路径长度。如果不存在这样的路径，请输出 _-1_。
[samples]
## Note
第一个样例中图的变化描述：
第二个样例中图的变化描述：
**Definitions**
Let $ G = (V, E) $ be a weighted directed graph, where:
- $ V = \{1, 2, \dots, n\} $ is the set of vertices.
- $ E = \{e_1, e_2, \dots, e_m\} $ is the set of directed edges, where each edge $ e_i = (a_i, b_i, c_i) $ has source $ a_i \in V $, target $ b_i \in V $, and initial weight $ c_i \in \mathbb{R}_{\geq 0} $.
Let $ Q $ be a sequence of $ q $ queries, each of one of two types:
- **Type 1**: Given $ v \in V $, compute the shortest path distance from vertex $ 1 $ to vertex $ v $.
- **Type 2**: Given $ v \in V $ and a set $ L = \{l_1, l_2, \dots, l_k\} \subseteq \{1, 2, \dots, m\} $ of distinct edge indices, update the weight of each edge $ e_{l_j} $ to $ 0 $.
**Constraints**
1. $ 1 \leq n, m \leq 10^5 $
2. $ 1 \leq q \leq 2000 $
3. For each edge $ e_i = (a_i, b_i, c_i) $: $ 1 \leq a_i, b_i \leq n $, $ 0 \leq c_i \leq 10^9 $
4. For each Type 2 query:
- All $ l_j \in L $ are distinct.
- Total number of edges updated across all Type 2 queries $ \leq 10^6 $
**Objective**
For each Type 1 query with parameter $ v $, compute:
$$
d(v) = \min \left\{ \sum_{e \in P} w(e) \,\middle|\, P \text{ is a path from } 1 \text{ to } v \right\}
$$
where $ w(e) $ is the current weight of edge $ e $ (initial or updated).
If no such path exists, output $ -1 $.
For each Type 2 query, update:
$$
w(e_{l_j}) \leftarrow 0 \quad \forall l_j \in L
$$
API Response (JSON)
{
"problem": {
"name": "D. Dynamic Shortest Path",
"description": {
"content": "You are given a weighted directed graph, consisting of _n_ vertices and _m_ edges. You should answer _q_ queries of two types: * _1 v_ — find the length of shortest path from vertex 1 to vertex _v_",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 10000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF843D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given a weighted directed graph, consisting of _n_ vertices and _m_ edges. You should answer _q_ queries of two types:\n\n* _1 v_ — find the length of shortest path from vertex 1 to vertex _v_...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个带权有向图，包含 #cf_span[n] 个顶点和 #cf_span[m] 条边。你需要回答 #cf_span[q] 个查询，分为两种类型：\n\n输入的第一行包含整数 #cf_span[n], #cf_span[m], #cf_span[q] (#cf_span[1 ≤ n, m ≤ 10^5], #cf_span[1 ≤ q ≤ 2000]) —— 分别表示图中的顶点数、边数和查询数。...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ G = (V, E) $ be a weighted directed graph, where: \n- $ V = \\{1, 2, \\dots, n\\} $ is the set of vertices. \n- $ E = \\{e_1, e_2, \\dots, e_m\\} $ is the set of directed edges, wher...",
"is_translate": false,
"language": "Formal"
}
]
}