問題一覧 > 通常問題

No.2640 traO Stamps

レベル : / AI推定難易度 : 1175 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 90
作問者 : zer0-star / テスター : noya2 ponjuice
お気に入りにしたユーザー ProblemId : 10669 / 自分の提出
問題文最終更新日: 2024-02-18 04:31:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
traP 作問ハッカソンコンテスト 002(day2) (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。