No.2640 traO Stamps
Problem Statement
The Tiger Kingdom has $N$ domains numbered $1, 2, \ldots, N$ and $M$ roads. The $i$-th road bidirectionally connects domain $A_i$ and domain $B_i$, and takes time $C_i$ to traverse. All domains can be reached from one another via the roads.
A stamp rally is being held in the Tiger Kingdom. There are $K+1$ stamps numbered $0, 1, \ldots, K$, and initially stamp $i$ is located in domain $S_i$. The goal of the stamp rally is to collect several stamps with consecutive numbers, in increasing order of their numbers.
Hoshimiya plans to go around the stamp rally several times. However, changes to the locations of the stamps are also planned at the same time.
You need to answer $Q$ queries. In the $i$-th query, integers $T_i, X_i, Y_i$ are given. Process the following.
- If $T_i = 1$:
- Stamp $X_i$ is moved to domain $Y_i$.
- If $T_i = 2$:
- Hoshimiya collects stamps $X_i, X_i + 1, \ldots, Y_i-1, Y_i$ in this order, moving so that the time taken is as small as possible.
- Output the time it takes from when Hoshimiya collects stamp $X_i$ until she collects stamp $Y_i$. The time taken to press a stamp is ignored.
Constraints
- $2 \leq N \leq 200$
- $1 \leq M \leq \frac{N(N-1)}{2}$
- $1 \leq K \leq 2 \times 10^5$
- $1 \leq S_i \leq N$
- $1 \leq A_i < B_i \leq N$
- $0 \leq C_i \leq 10^9$
- If $i \neq j$, then $(A_i, B_i) \neq (A_j, B_j)$
- All domains can be reached from one another via the roads
- $1 \leq Q \leq 10^5$
- $T_i = 1$ or $T_i = 2$
- If $T_i = 1$:
- $0 \leq X_i \leq K$
- $1 \leq Y_i \leq N$
- If $T_i = 2$:
- $0 \leq X_i \leq Y_i \leq K$
- $T_i = 2$ in at least $1$ query
Input
$N\ M\ K$ $S_0\ S_1\ \cdots\ S_K$ $A_1\ B_1\ C_1$ $\vdots$ $A_M\ B_M\ C_M$ $Q$ $T_1\ X_1\ Y_1$ $\vdots$ $T_Q\ X_Q\ Y_Q$
Output
For each query with $T_i = 2$, output the answer on $1$ line.
Sample
Sample 1
Input
4 5 3 1 2 4 2 1 2 1 3 4 2 2 4 5 1 3 2 2 3 7 6 2 0 3 1 1 3 2 0 2 2 1 1 1 0 2 2 0 3
Output
11 4 0 10
The graph given in this case looks like the figure above.
In the $1$st query, to collect stamps $0$ through $3$, Hoshimiya visits the domains in the order $1 \to 2 \to 4 \to 2$. The time it takes Hoshimiya to collect all the stamps is $11$.
In the $2$nd query, stamp $1$ is moved to domain $3$. Therefore, in the $3$rd query, Hoshimiya visits the domains in the order $1 \to 3 \to 4$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2