No.3087 University Coloring
タグ : / 解いたユーザー数 89
作問者 :
amentorimaru
Problem Statement
Koyaso National University has $N$ plazas, numbered $1,2,\dots, N$. Each plaza has a Koyaso statue. Initially, none of the Koyaso statues are painted.
There are also $M$ passages, numbered $1,2,\dots , M$. Passage $i$ connects plazas $a,b$ and has length $c$. It is guaranteed that every plaza can be reached from plaza $1$ by traversing passages $0$ or more times.
Yu is initially at plaza $1$, and has painted the Koyaso statue in plaza $1$ blue.
From now on, Yu may perform the following actions any number of times. Regarding the "card pile" mentioned in the description, the pile initially contains no cards.
- Action $1$: Choose a plaza that is directly connected to the current plaza by a passage and whose Koyaso statue has not been painted yet, move there, and paint the Koyaso statue at the destination blue. At this time, letting $x$ be the number of the passage used, place $1$ card with $x$ written on it on top of the card pile.
Action $2$: Paint the Koyaso statue in the current plaza purple, remove the top card of the card pile, and traverse the passage whose number is written on the removed card. It can be proved that one end of this passage is always the current plaza (that is, this passage can be traversed from the current plaza).
However, if no cards remain in the pile, Yu declares the end immediately after painting the Koyaso statue and performs no further actions.
Find the maximum possible total distance Yu has moved at the time Yu declares the end. Movement within a plaza is not counted.
Input
$N\ M$ $a_1\ b_1\ c_1$ $a_2\ b_2\ c_2$ $\vdots$ $a_M\ b_M\ c_M$
Constraints
- $2\le N\le 2\times 10^5$
- $1\le M\le \min(\frac{N(N-1)}{2},2\times 10^5)$
- $1\le a_i< b_i \le N$
- $1\le c_i \le 10^9$
- $a_i \neq b_i$
- If $i\neq j$, then $(a_i,b_i)\neq (a_j,b_j)$
- Every plaza can be reached from plaza $1$ by traversing passages $0$ or more times.
- All inputs are integers.
Output
Print a newline at the end.
Sample
Sample 1
Input
3 3 1 2 1 2 3 2 1 3 3
Output
10
For example, the following sequences of actions are possible.
- Plaza $1$ → (Action $1$) Plaza $2$ → (Action $1$) Plaza $3$ → (Action $2$) Plaza $2$ → (Action $2$) Plaza $1$ → (Action $2$) End
- Plaza $1$ → (Action $1$) Plaza $3$ → (Action $1$) Plaza $2$ → (Action $2$) Plaza $3$ → (Action $2$) Plaza $1$ → (Action $2$) End
For the former sequence of actions, the total distance moved is $6$. For the latter, it is $10$. Since the total distance moved cannot exceed $10$ for any sequence of moves, print $10$.
Sample 2
Input
4 5 1 2 4 2 3 6 3 4 8 1 3 10 2 4 10
Output
56
Sample 3
Input
6 5 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000
Output
10000000000
Note that the answer may not fit in a $32$-bit integer type.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。