Problem B
Leiðinda rigning
Languages
en
is
Atli is trying to get home, but like most days it’s raining
cats and dogs in Reykjavík. Thus he is trying to plan his route
such that he’ll minimize how wet he gets. More specifically he
has located $n$ shelters
from the rain which he can let himself dry under. He has also
located $m$ routes between
these shelters and for each route he has figured out how wet
he’ll get travelling that route. Additionally some of these
shelters will be bus stops. To get home Atli has to travel
between shelters until he gets to a bus stop, from which he can
travel all the way home. Atli will always travel home in a way
that minimizes how wet he gets along the way.
Atli isn’t always travelling from the same place and bus
stops aren’t set in stone either. Thus there will be
$q$ queries, each one
being one of three types. A query can say that a particular
shelter is now a bus stop, say that a particular shelter is no
longer a bus stop or ask for how wet Atli will get travelling
home from some particular shelter. At the start only shelter
$1$ is a bus stop.
Atli solved this problem long ago of course, but he won’t tell anyone the solution since that would spoil the fun.
Input
The first line of the input contains two integers $1 \leq n \leq 5 \cdot 10^4$, the number of shelters and $0 \leq m \leq 10^5$, the number of routes between them. Next there are $m$ lines, each describing a route between two shelters. Each of those lines contains three integers $1 \leq a, b \leq n$ and $0 \leq w \leq 10^9$. This means there is a route from shelter $a$ to shelter $b$ which makes Atli $w$ wet from travelling along it. Routes can be travelled in either direction and $w$ does not change depending on the direction. Next there is a line with an integer $1 \leq q \leq 5 \cdot 10^4$, the number of queries. Finally there are $q$ lines, each containing two integers $1 \leq t \leq 3$ and $1 \leq x \leq n$. If $t = 1$ this means that a bus stop opens at shelter $x$, in this case $x$ will not already be a bus stop. If $t = 2$ this means that the bus stop at shelter $x$ closes, in this case $x$ will be a bus stop. Finally if $t = 3$ the program should print how wet Atli gets at most when travelling home from shelter $x$.
It is guaranteed that it will always be possible to travel from any shelter to any other. Furthermore there will always be at least one working bus stop at any given time.
Output
How wet Atli gets should be printed for every query of type $t = 3$.
Sample Input 1 | Sample Output 1 |
---|---|
4 5 1 2 5 1 3 4 2 3 2 2 4 3 3 4 1 9 3 2 1 4 3 2 3 3 1 3 3 3 2 1 2 4 3 1 |
4 2 1 0 4 |