首頁  題目列表  狀態列表  排行榜  註冊  帳號: 密碼:
公告:支援C++11 (2014/08/18 21:39)
Problem 0149 : 轎夫
0149 -- 轎夫
Case Time Limit: 3000 ms    Memory Limit: 131072 KB
Total Testdata Count: 28
AC/Submit: 5/37    AC/Submit Users: 4/10

[回到列表]
題目敘述

經過千辛萬苦的拔涉,你,もも,一個弱雞勇者,終於到了雲南。
雲南有個特點,就是山很多

但是你並不很清楚的知道「那一位」到底被關在哪裡。所以你只好雇兩個轎夫,扛著你到處跑來跑去。

每條路會連接兩個山頭,而且每條山路都有他的難易度,有可能是一馬平川,有可能兩個轎夫要扛著你攀岩垂降,所以轎夫們會根據難易度訂定價錢。

而雲南的轎夫跟京城的收費方式不一樣,他們認為便宜的路就不跟你收錢了,他們只收最貴的那條路,吝嗇的你決定好好利用這點,帶他們走最貴的那一段最便宜的那種走法……

輸入說明

第一行給定$V,E,Q$,($|V|$個山頭, $|E|$條山路),$Q$筆詢問。
接下來E行給定$a,b,cost$給定每一段山路的兩端端點,以及這一段山路的價錢。
接下來Q行每次問一組頂點$(u, v)$,問u到v所有山路中最貴那一段最小是多少。

分A,B,C,D四組測資
A(10 points) : $|V| \leq 500$
B(25 points) : $Q = 1$
C(30 points) : $|E| = |V|-1$
D(35 points) : no limits
對所有測資
$V,E \leq 2 \times 10^5$
$Q \leq 10^5$
$1 \leq a,b,u,v \leq V$
$0\leq cost \leq 2147483647$

輸出說明

對每一筆詢問輸出$u$到$v$所有山路中最貴那一段最小是多少。

範例輸入

4 4 2
1 2 5
1 3 2
2 3 3
3 4 100
1 2
2 4


範例輸出

3
100


備註

對第一筆Query可以走1→3→2
第二筆Query可以走4→3→2

測資

測資組A : 1~7 (7筆測資),10 分
測資組B : 8~12 (5筆測資),25 分
測資組C : 13~18 (6筆測資),30 分
測資組D : 19~28 (10筆測資),35 分
[回到列表]