过路费

问题描述

在某个遥远的国家里，有 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 行，每行一个整数，分别表示每个询问需要上交的最少过路费用。输入数据保证所有的城市都是连通的。

样例输入

4 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；

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

struct record{
    int a,b,w;
};

int n,m,q,tot;
int s[10001],t[10001],ans[10001];
int head[10001],next[20001],data[20001],value[20001];
int f[10001];
int vis[10001],weight[10001],father[10001];
record method[100001];

int find(int x){
    if (f[x]==x)
        return x;
    else
        return find(f[x]);
}

bool cmp(record x,record y){
    return x.w<y.w;
}

void build(int x,int y,int w){
    tot++;
    next[tot]=head[x];
    data[tot]=y;
    value[tot]=w;
    head[x]=tot;
    tot++;
    next[tot]=head[y];
    data[tot]=x;
    value[tot]=w;
    head[y]=tot;
}

void kruscal(){
    int i=1,s=0,f1,f2;
    sort(method+1,method+m+1,cmp);
    for (i=1;i<=n;i++)
        f[i]=i;
    for (i=1;s!=n-1;i++){
        f1=find(method[i].a);
        f2=find(method[i].b);
        if (f1!=f2){
            s++;
            f[f1]=f2;
            build(method[i].a,method[i].b,method[i].w);
        }
    }
}

int doit(int x,int p,int y){
    int now=0;
    for (;x!=p;x=father[x])
        now=max(now,weight[x]);
    for (;y!=p;y=father[y])
        now=max(now,weight[y]);
    return now;
}

void lca(int x){
    int i,y=head[x];
    vis[x]=1;
    for (;y!=0;y=next[y])
        if (vis[data[y]]==0){
            weight[data[y]]=value[y];
            father[data[y]]=x;
            lca(data[y]);
            f[data[y]]=x;
        }
    for (i=1;i<=q;i++){
        if (s[i]==x && vis[t[i]]==1)
            ans[i]=doit(x,find(t[i]),t[i]);
        if (t[i]==x && vis[s[i]]==1)
            ans[i]=doit(s[i],find(s[i]),x);
    }
}

int main(){
    int i;
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++)
        scanf("%d%d%d",&method[i].a,&method[i].b,&method[i].w);
        
    kruscal();
    
    scanf("%d",&q);
    for (i=1;i<=q;i++)
        scanf("%d%d",&s[i],&t[i]);
    memset(vis,0,sizeof(vis));
    for (i=1;i<=n;i++)
        f[i]=i;
    lca(1);
    
    for (i=1;i<=q;i++)
        printf("%d\n",ans[i]);
    return 0;   
}

推荐阅读更多精彩内容