Travel
For each test case, the first line consists of three integers n,m and q where n≤20000,m≤100000,q≤5000. The Undirected Kingdom has n cities and mbidirectional roads, and there are q queries.
Each of the following m lines consists of three integers a,b and d where a,b∈{1,...,n} and d≤100000. It takes Jack d minutes to travel from city a to city band vice versa.
Then q lines follow. Each of them is a query consisting of an integer x where x is the time limit before Jack goes berserk.
Note that (a,b) and (b,a) are counted as different pairs and a and b must be different cities.
5 5 3
2 3 6334
1 5 15724
3 5 5705
4 3 12382
1 3 21726
6000
10000
13000
6
12
///
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll;
#define mem(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,127,sizeof(a));
#define TS printf("111111\n");
#define FOR(i,a,b) for( int i=a;i<=b;i++)
#define FORJ(i,a,b) for(int i=a;i>=b;i--)
#define READ(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inf 100000
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//****************************************
#define maxn 1000000+50 struct ss
{
int u,v,w;
bool operator <(const ss &x)const{
return w<x.w;
}
}a[maxn]; ll ans[maxn];
int num[maxn],parent[maxn],n,m,q; struct sss
{
int v,id;
bool operator <(const sss &x)const{
return v<x.v;
}
}Ans[maxn]; int finds(int x){
if(x!=parent[x])parent[x]=finds(parent[x]);
return parent[x];
}
void init()
{
FOR(i,,n){parent[i]=i;num[i]=;}
mem(ans);
}
int main()
{ int T=read();
while(T--)
{ scanf("%d%d%d",&n,&m,&q); FOR(i,,m)
{
scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
}
sort(a+,a+m+);
// FOR(i,1,m){cout<<a[i].u<<" "<<a[i].v<<" "<<a[i].w<<endl;} FOR(i,,q)
{
scanf("%d",&Ans[i].v);
Ans[i].id=i;
} sort(Ans+,Ans+q+); init();
//FOR(i,1,q)cout<<Ans[i].v<<" "<<Ans[i].id<<endl;
ll aa=;
int j=;
FOR(i,,q)
{
while(j<=m&&Ans[i].v>=a[j].w)
{
int fx=finds(a[j].u);
int fy=finds(a[j].v);
if(fx!=fy)
{
parent[fy]=fx;
aa+=num[fx]*num[fy];
num[fx]+=num[fy];
}
j++;
}
ans[Ans[i].id]=aa*;
}
for(int i=;i<=q;i++)
printf("%I64d\n", ans[i]);
}
return ;
}
代码
给你一个图,n个点,m条边,并有边权值,q个询问,每个询问是一个限制值,问你多少对不同的(S,T)路径上的最小权值不超过这个限制值,(S,T)与(T,S)是不同的。