時間限制: 1 s 空間限制: 256000 KB 題目等級 : 大師 Master 題目描述 Description
在某個遙遠的國家裡，有 n個城市。編號為 1,2,3,…,n。這個國家的政府修建了m 條雙向道路，每條道路連接著兩個城市。政府規定從城市 S 到城市T需要收取的過路費為所經過城市之間道路長度的最大值。如：A到B長度為 2，B到C 長度為3，那麼開車從 A經過 B到C 需要上交的過路費為 3。
佳佳是個做生意的人，需要經常開車從任意一個城市到另外一個城市，因此他需要頻繁地上交過路費，由於忙於做生意，所以他無時間來尋找交過路費最低的行駛路線。然而， 當他交的過路費越多他的心情就變得越糟糕。 作為秘書的你，需要每次根據老板的起止城市，提供給他從開始城市到達目的城市，最少需要上交多少過路費。
第一行是兩個整數 n 和m，分別表示城市的個數以及道路的條數。
接下來 m 行，每行包含三個整數 a，b，w（1≤a，b≤n，0≤w≤10^9），表示a與b之間有一條長度為 w的道路。
接著有一行為一個整數 q，表示佳佳發出的詢問個數。
再接下來 q行，每一行包含兩個整數 S，T（1≤S,T≤n，S≠T）, 表示開始城市S 和目的城市T。
輸出共q行，每行一個整數，分別表示每個詢問需要上交的最少過路費用。輸入數據保證所有的城市都是連通的。
樣例輸入 Sample Input4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1
20
20
對於 30%的數據，滿足 1≤ n≤1000，1≤m≤10000，1≤q≤100；
對於 50%的數據，滿足 1≤ n≤10000，1≤m≤10000，1≤q≤10000；
對於 100%的數據，滿足 1≤ n≤10000，1≤m≤100000，1≤q≤10000；
1 #include<cstdio>
2 #include<algorithm>
3 #include<iostream>
4 using namespace std;
5 #define N 400100
6 int fa[N],head[N],next[N],tot=0;
7 int dep[N],par[N],dist[N];
8 struct node{
9 int u,v,w;
10 }e[N],l[N];
11 int find(int x){
12 return fa[x]==x?x:fa[x]=find(fa[x]);
13 }
14 void build(int u,int v,int w){
15 l[++tot].v=v;
16 l[tot].w=w;
17 next[tot]=head[u];
18 head[u]=tot;
19 }
20 void dfs(int f,int parent,int de,int dis){
21 par[f]=parent;//記錄當前點的最近父節點
22 dist[f]=dis;//記錄當前點的單邊的邊權值
23 dep[f]=de;//記錄當前點的深度
24 for(int i=head[f];i;i=next[i]){
25 int v=l[i].v;//尋找方向
26 if(v!=parent)//爆搜出樹的深度
27 dfs(v,f,de+1,l[i].w);
28 }
29 }
30 int lca(int f,int t){
31 int ans=0;
32 while(dep[f]>dep[t])
33 ans=max(ans,dist[f]),f=par[f];
34 while(dep[f]<dep[t])
35 ans=max(ans,dist[t]),t=par[t];
36 /*盡量保持f,t同一深度*/
37 while(f!=t){//f,t一起往上找
38 ans=max(ans,dist[f]);
39 ans=max(ans,dist[t]);
40 f=par[f];
41 t=par[t];
42 }
43 return ans;
44 }
45 bool cmp(node a,node b){
46 return a.w<b.w;
47 }
48 int main()
49 {
50 freopen("sh.in","r",stdin);
51 int n,m,q;
52 scanf("%d%d",&n,&m);
53 for(int i=1;i<=n;i++) fa[i]=i;
54 for(int i=1;i<=m;i++)
55 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
56 sort(e+1,e+m+1,cmp);
57 for(int i=1;i<=m;i++){
58 int x=find(e[i].u);
59 int y=find(e[i].v);
60 if(x!=y){
61 fa[x]=y;
62 build(e[i].u,e[i].v,e[i].w);
63 build(e[i].v,e[i].u,e[i].w);
64 }
65 }
66 dfs(1,0,0,0);//遍歷出深度
67 scanf("%d",&q);
68 for(int i=1,from,to;i<=q;i++){
69 scanf("%d%d",&from,&to);
70 printf("%d\n",lca(from,to));
71 }
72 return 0;
73 }
