題目描述?Description
? ? 在某個遙遠的國家里，有 n個城市。編號為 1,2,3,…,n。這個國家的政府修建了m 條雙向道路，每條道路連接著兩個城市。政府規定從城市 S 到城市T需要收取的過路費為所經過城市之間道路長度的最大值。如：A到B長度為 2，B到C 長度為3，那么開車從 A經過 B到C 需要上交的過路費為 3。
? ? 佳佳是個做生意的人，需要經常開車從任意一個城市到另外一個城市，因此他需要頻繁地上交過路費，由于忙于做生意，所以他無時間來尋找交過路費最低的行駛路線。然而， 當他交的過路費越多他的心情就變得越糟糕。 作為秘書的你，需要每次根據老板的起止城市，提供給他從開始城市到達目的城市，最少需要上交多少過路費。
輸入描述?Input Description
? ? 第一行是兩個整數 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。
輸出描述?Output Description
? ? 輸出共q行，每行一個整數，分別表示每個詢問需要上交的最少過路費用。輸入數據保證所有的城市都是連通的。
樣例輸入?Sample Input
4 5?
1 2 10?
1 3 20?
1 4 100?
2 4 30?
3 4 10?
2?
1 4?
4 1
樣例輸出?Sample Output
20?
20
數據范圍及提示?Data Size & Hint
vscode免費嗎。對于 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；
題解：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn=10000+5; const int maxm=200000+5; int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int n,m,q,num; int father[maxn],dep[maxn],nxt[maxm],head[maxn],f[maxn],dis[maxn]; bool vis[maxn]; struct node {int from,to,dist;bool operator < (const node& j) const {return dist<j.dist;} }e[maxm],c[maxm]; void add(int from,int to,int dist) {e[++num].from=from;e[num].to=to;e[num].dist=dist;nxt[num]=head[from];head[from]=num; } int find(int x) {if(x!=father[x]) father[x]=find(father[x]);return father[x]; } void dfs(int x) {vis[x]=1;for(int i=head[x];i;i=nxt[i]){int to=e[i].to;if(!vis[to]){f[to]=x;dep[to]=dep[x]+1;dis[to]=e[i].dist;dfs(to);}} } int lca(int x,int y) {int maxx=0;if(dep[x]>dep[y]) swap(x,y);while(dep[x]<dep[y]){maxx=max(maxx,dis[y]);y=f[y];}while(x!=y){maxx=max(maxx,dis[x]);maxx=max(maxx,dis[y]);x=f[x];y=f[y];}return maxx; }int main() {n=read();m=read();for(int i=1;i<=n;i++) father[i]=i;for(int i=1;i<=m;i++){c[i].from=read();c[i].to=read();c[i].dist=read();}sort(c+1,c+1+m);for(int i=1;i<=m;i++){int x=find(c[i].from);int y=find(c[i].to);if(x!=y){father[x]=y;add(c[i].from,c[i].to,c[i].dist);add(c[i].to,c[i].from,c[i].dist);}}dfs(1);q=read();for(int i=1;i<=q;i++){int a,b;a=read();b=read();printf("%d\n",lca(a,b));}return 0; }
?
