No.2915 Edge Update Value Maximization
タグ : / 解いたユーザー数 16
作問者 : 👑
p-adic
/ テスター :
Shirotsume
Problem Statement
At the beginning of the input, $3$ positive integers $N, M, Q$ are given.
A village has $N$ squares and $M$ one-way roads connecting them.
The squares are numbered by the positive integers $i$ not exceeding $N$, and each is called square $i$.
The roads are numbered by the positive integers $j$ not exceeding $M$, and each is called road $j$. Road $j$ goes from square $u_j$ to square $v_j$ ($u_j, v_j$ are distinct positive integers not exceeding $N$).
Chokushin Daisuki bot is a bot that loves going straight along the roads of this village. Chokushin Daisuki bot has an integer value called exhilaration, which changes according to the roads it has gone along.
Specifically, for each positive integer $j$ not exceeding $M$, when Chokushin Daisuki bot goes along road $j$ from square $u_j$ to square $v_j$, the integer $w_j$ (not necessarily non-negative) is added to its exhilaration.
However, it is guaranteed that there is no route that starts from some square, goes only along roads, and returns to the original square such that the final exhilaration is strictly greater than the exhilaration at the time of departure.
Initially, no road is broken, but roads get broken and repaired by the $Q$ queries described below.
Each query is given as a positive integer $j$ not exceeding $M$. When a query is $j$, it is processed as follows.
- First, if road $j$ is not broken, break road $j$; if road $j$ is broken, repair road $j$.
- Next, determine whether there exists a route from square $1$ to square $N$ going only along roads that are not broken.
- Then, if one exists, find the maximum possible final exhilaration when Chokushin Daisuki bot starts with exhilaration $0$ and goes along the roads following such a route.
The results of 2 and 3 are called the answer to this query.
Process all the queries in the given order.
Input
For each positive integer $q$ not exceeding $Q$, let $j_q$ denote the $q$-th query.
The input is given from standard input in $2 + M$ lines in the following format:
- The $1$st line contains $N, M, Q$ separated by single spaces.
- For each positive integer $j$ not exceeding $M$, line $1 + j$ contains $u_j , v_j , w_j$ separated by single spaces.
- Line $2 + M$ contains $j_q$ for each positive integer $q$ not exceeding $Q$, in increasing order of $q$, separated by single spaces.
$N$ $M$ $Q$ $u_1$ $v_1$ $w_1$ $\vdots$ $u_M$ $v_M$ $w_M$ $j_1$ $\cdots$ $j_Q$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $2 \leq N \leq 10^3$.
- $M$ is an integer satisfying $1 \leq M \leq 10^3$.
- For any positive integer $j$ not exceeding $M$,
- $u_j, v_j$ are integers satisfying $1 \leq u_j \leq N$, $1 \leq v_j \leq N$, and $u_j \neq v_j$.
- $w_j$ is an integer satisfying $- 10^3 \leq w_j \leq 10^3$.
- There is no route that starts from some square, goes only along roads, and returns to the original square such that the final exhilaration is strictly greater than the exhilaration at the time of departure.
- $Q$ is an integer satisfying $1 \leq Q \leq 10^3$.
- For any positive integer $q$ not exceeding $Q$, $j_q$ is an integer satisfying $1 \leq j_q \leq M$.
Output
For each positive integer $q$ not exceeding $Q$, output the answer to the $q$-th query on line $q$ in the following format.
- If there exists a route from square $1$ to square $N$ going only along roads that are not broken, output the maximum possible final exhilaration when Chokushin Daisuki bot starts with exhilaration $0$ and goes along the roads following such a route.
- Otherwise, output
NaN.
It can be proved under the constraints of this problem that the maximum exists in the former case.
Print a newline at the end.
Sample
Sample 1
Input
2 1 2 1 2 0 1 1
Output
NaN 0
There are squares $1,2$. Initially, they are connected by road $1$ as
$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 $
.
The value of the $1$st query is $j_1 = 1$. First, road $1$ is broken. Then no unbroken road remains, so there is no route from square $1$ to square $2$ going only along roads that are not broken.
Therefore, output NaN.
The value of the $2$nd query is $j_2 = 1$. First, road $1$ is repaired, and the squares become connected as
$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 $
. Then the only route from square $1$ to square $2$ is
$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 $
, and the exhilaration of Chokushin Daisuki bot upon reaching square $2$ by this route is $0$.
Since $Q = 2$ here, all the queries have now been processed.
Sample 2
Input
3 4 2 1 2 0 2 3 1 3 2 -3 2 3 2 3 4
Note that multiple roads may connect the same pair of squares, as in this case.
Output
2 1
There are squares $1,2,3$. Initially, they are connected by roads $1,2,3,4$ as
$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 \begin{array}{c} \displaystyle \stackrel{w_2 = 1}{\longrightarrow} \\ \displaystyle \stackrel{w_3 = -3}{\longleftarrow} \\ \displaystyle \stackrel{w_4 = 2}{\longrightarrow} \end{array} 3 $
.
The value of the $1$st query is $j_1 = 3$. First, road $3$ is broken, and the squares become connected as
$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 \begin{array}{c} \displaystyle \stackrel{w_2 = 1}{\longrightarrow} \\ \displaystyle \stackrel{w_4 = 2}{\longrightarrow} \end{array} 3 $
. Then the routes from square $1$ to square $3$ are the following $2$:
$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 \stackrel{w_2 = 1}{\longrightarrow} 3 $
and
$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 \stackrel{w_4 = 2}{\longrightarrow} 3 $
, and the exhilaration of Chokushin Daisuki bot upon reaching square $3$ by these routes is $0 + 1 = 1$ and $0 + 2 = 2$, respectively.
The value of the $2$nd query is $j_2 = 4$. First, road $4$ is broken, and the squares become connected as
$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 \stackrel{w_2 = 1}{\longrightarrow} 3 $
. Then the only route from square $1$ to square $3$ is
$\displaystyle 1 \stackrel{w_1 = 0}{\longrightarrow} 2 \stackrel{w_2 = 1}{\longrightarrow} 3 $
, and the exhilaration of Chokushin Daisuki bot upon reaching square $3$ by this route is $0 + 1 = 1$.
Since $Q = 2$ here, all the queries have now been processed.
Sample 3
Input
4 4 2 1 2 -1 2 3 -1 3 4 -1 1 4 1 4 4
Note that the value of $w_j$ for a positive integer $j$ not exceeding $M$ may be negative, as in this case.
Output
-3 1
There are squares $1,2,3,4$. Initially, they are connected by roads $1,2,3,4$ as
$\displaystyle \begin{array}{rcl} \displaystyle 1 &\displaystyle \stackrel{w_4 = 1}{\longrightarrow} &\displaystyle 4 \\ \displaystyle {}_{w_1 = -1} \downarrow &\displaystyle &\displaystyle \uparrow_{w_3 = -1} \\ \displaystyle 2 &\displaystyle \stackrel{w_2 = -1}{\longrightarrow} &\displaystyle 3 \end{array} $
.
The value of the $1$st query is $j_1 = 4$. First, road $4$ is broken, and the squares become connected as
$\displaystyle \begin{array}{rcl} \displaystyle 1 &\displaystyle &\displaystyle 4 \\ \displaystyle {}_{w_1 = -1} \downarrow &\displaystyle &\displaystyle \uparrow_{w_3 = -1} \\ \displaystyle 2 &\displaystyle \stackrel{w_2 = -1}{\longrightarrow} &\displaystyle 3 \end{array} $
. Then the only route from square $1$ to square $4$ is
$\displaystyle 1 \stackrel{w_1 = -1}{\longrightarrow} 2 \stackrel{w_2 = -1}{\longrightarrow} 3 \stackrel{w_3 = -1}{\longrightarrow} 4 $
, and the exhilaration of Chokushin Daisuki bot upon reaching square $4$ by this route is $(-1) + (-1) + (-1) = -3$.
The value of the $2$nd query is $j_2 = 4$. First, road $4$ is repaired, and the squares become connected as
$\displaystyle \begin{array}{rcl} \displaystyle 1 &\displaystyle \stackrel{w_4 = 1}{\longrightarrow} &\displaystyle 4 \\ \displaystyle {}_{w_1 = -1} \downarrow &\displaystyle &\displaystyle \uparrow_{w_3 = -1} \\ \displaystyle 2 &\displaystyle \stackrel{w_2 = -1}{\longrightarrow} &\displaystyle 3 \end{array} $
. Then the routes from square $1$ to square $4$ are the following $2$:
$\displaystyle 1 \stackrel{w_4 = 1}{\longrightarrow} 4 $
and
$\displaystyle 1 \stackrel{w_1 = -1}{\longrightarrow} 2 \stackrel{w_2 = -1}{\longrightarrow} 3 \stackrel{w_3 = -1}{\longrightarrow} 4 $
, and the exhilaration of Chokushin Daisuki bot upon reaching square $4$ by these routes is $1$ and $(-1) + (-1) + (-1) = -3$, respectively.
Since $Q = 2$ here, all the queries have now been processed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。