A9742. Tourists
编程题
普及/提高-
知识点
题目描述
There are $n$ cities in Cyberland, numbered from $1$ to $n$ , connected by $m$ bidirectional roads. The $j$ -th road connects city $a_{j}$ and $b_{j}$ .
For tourists, souvenirs are sold in every city of Cyberland. In particular, city $i$ sell it at a price of $w_{i}$ .
Now there are $q$ queries for you to handle. There are two types of queries:
- "C $a$ $w$ ": The price in city $a$ is changed to $w$ .
- "A $a$ $b$ ": Now a tourist will travel from city $a$ to $b$ . He will choose a route, he also doesn't want to visit a city twice. He will buy souvenirs at the city where the souvenirs are the cheapest (possibly exactly at city $a$ or $b$ ). You should output the minimum possible price that he can buy the souvenirs during his travel.
More formally, we can define routes as follow:
- A route is a sequence of cities $\[x_{1},x_{2},...,x_{k}\]$ , where $k$ is a certain positive integer.
- For any $1<=i<j<=k,x_{i}≠x_{j}$ .
- For any $1<=i<k$ , there is a road connecting $x_{i}$ and $x_{i+1}$ .
- The minimum price of the route is $min(w_{x1},w_{x2},...,w_{xk})$ .
- The required answer is the minimum value of the minimum prices of all valid routes from $a$ to $b$ .
For tourists, souvenirs are sold in every city of Cyberland. In particular, city $i$ sell it at a price of $w_{i}$ .
Now there are $q$ queries for you to handle. There are two types of queries:
- "C $a$ $w$ ": The price in city $a$ is changed to $w$ .
- "A $a$ $b$ ": Now a tourist will travel from city $a$ to $b$ . He will choose a route, he also doesn't want to visit a city twice. He will buy souvenirs at the city where the souvenirs are the cheapest (possibly exactly at city $a$ or $b$ ). You should output the minimum possible price that he can buy the souvenirs during his travel.
More formally, we can define routes as follow:
- A route is a sequence of cities $\[x_{1},x_{2},...,x_{k}\]$ , where $k$ is a certain positive integer.
- For any $1<=i<j<=k,x_{i}≠x_{j}$ .
- For any $1<=i<k$ , there is a road connecting $x_{i}$ and $x_{i+1}$ .
- The minimum price of the route is $min(w_{x1},w_{x2},...,w_{xk})$ .
- The required answer is the minimum value of the minimum prices of all valid routes from $a$ to $b$ .
输入格式
The first line of input contains three integers $n, m, q (1 \leq n, m, q \leq 10^5)$, separated by a single space.
Next n lines contain integers $w_i (1 \leq w_i \leq 10^9)$.
Next m lines contain pairs of space-separated integers $a_j$ and $b_j$ $(1 \leq a_j, b_j \leq n, aj \neq bj)$.
It is guaranteed that there is at most one road connecting the same pair of cities. There is always at least one valid route between any two cities.
Next $q$ lines each describe a query. The format is "C a w" or "A a b" $(1 \leq a, b \leq n, 1 \leq w \leq 10^9)$.
Next n lines contain integers $w_i (1 \leq w_i \leq 10^9)$.
Next m lines contain pairs of space-separated integers $a_j$ and $b_j$ $(1 \leq a_j, b_j \leq n, aj \neq bj)$.
It is guaranteed that there is at most one road connecting the same pair of cities. There is always at least one valid route between any two cities.
Next $q$ lines each describe a query. The format is "C a w" or "A a b" $(1 \leq a, b \leq n, 1 \leq w \leq 10^9)$.
输出格式
For each query of type "A", output the corresponding answer.
输入输出样例
输入 #1
3 3 3 1 2 3 1 2 2 3 1 3 A 2 3 C 1 5 A 2 3
输出 #1
1 2
输入 #2
7 9 4 1 2 3 4 5 6 7 1 2 2 5 1 5 2 3 3 4 2 4 5 6 6 7 5 7 A 2 3 A 6 4 A 6 7 A 3 3
输出 #2
2 1 5 3
说明/提示
There are $n$ cities in Cyberland, numbered from $1$ to $n$ , connected by $m$ bidirectional roads. The $j$ -th road connects city $a_{j}$ and $b_{j}$ .
For tourists, souvenirs are sold in every city of Cyberland. In particular, city $i$ sell it at a price of $w_{i}$ .
Now there are $q$ queries for you to handle. There are two types of queries:
- "C $a$ $w$ ": The price in city $a$ is changed to $w$ .
- "A $a$ $b$ ": Now a tourist will travel from city $a$ to $b$ . He will choose a route, he also doesn't want to visit a city twice. He will buy souvenirs at the city where the souvenirs are the cheapest (possibly exactly at city $a$ or $b$ ). You should output the minimum possible price that he can buy the souvenirs during his travel.
More formally, we can define routes as follow:
- A route is a sequence of cities $\[x_{1},x_{2},...,x_{k}\]$ , where $k$ is a certain positive integer.
- For any $1<=i<j<=k,x_{i}≠x_{j}$ .
- For any $1<=i<k$ , there is a road connecting $x_{i}$ and $x_{i+1}$ .
- The minimum price of the route is $min(w_{x1},w_{x2},...,w_{xk})$ .
- The required answer is the minimum value of the minimum prices of all valid routes from $a$ to $b$ .
For tourists, souvenirs are sold in every city of Cyberland. In particular, city $i$ sell it at a price of $w_{i}$ .
Now there are $q$ queries for you to handle. There are two types of queries:
- "C $a$ $w$ ": The price in city $a$ is changed to $w$ .
- "A $a$ $b$ ": Now a tourist will travel from city $a$ to $b$ . He will choose a route, he also doesn't want to visit a city twice. He will buy souvenirs at the city where the souvenirs are the cheapest (possibly exactly at city $a$ or $b$ ). You should output the minimum possible price that he can buy the souvenirs during his travel.
More formally, we can define routes as follow:
- A route is a sequence of cities $\[x_{1},x_{2},...,x_{k}\]$ , where $k$ is a certain positive integer.
- For any $1<=i<j<=k,x_{i}≠x_{j}$ .
- For any $1<=i<k$ , there is a road connecting $x_{i}$ and $x_{i+1}$ .
- The minimum price of the route is $min(w_{x1},w_{x2},...,w_{xk})$ .
- The required answer is the minimum value of the minimum prices of all valid routes from $a$ to $b$ .