代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#define MN 200000
#define MM 400000
#define MQ 100000
typedef long long LL;
int n,m,q,k,s;
int hd[MN+5],dis[MN+5],fa[MN+5];
int to[MM*2+5],val[MM*2+5],nxt[MM*2+5],rn=0;
bool vis[MN+5];
struct edge{int u,v,l,a;}e[MM+5];
struct ques{int v,p,i,a;}qu[MQ+5];
struct node{int u,d;bool operator<(const node b)const{return d>b.d;}};
bool cmp1(edge a,edge b){return a.a>b.a;}
bool cmp2(ques a,ques b){return a.p>b.p;}
bool cmp3(ques a,ques b){return a.i<b.i;}
inline void add(int u,int v,int w){
	++rn;nxt[rn]=hd[u];hd[u]=rn;to[rn]=v;val[rn]=w;
}
int gfa(int u){return fa[u]==u?fa[u]:fa[u]=gfa(fa[u]);}
void uni(int u,int v){
	u=gfa(u),v=gfa(v); if(u==v) return;
	dis[u]=std::min(dis[u],dis[v]); fa[v]=u;
}
void dij(int S){
	memset(vis,false,sizeof(vis));
	memset(dis,0x7f,sizeof(dis));
	std::priority_queue<node> Q;
	dis[S]=0; Q.push((node){S,dis[S]});
	while(!Q.empty()){
		node u=Q.top(); Q.pop();
		if(vis[u.u]) continue; vis[u.u]=true;
		for(int i=hd[u.u];i!=-1;i=nxt[i]){
			if(vis[to[i]]) continue;
			if(dis[to[i]]>dis[u.u]+val[i]){
				dis[to[i]]=dis[u.u]+val[i];
				Q.push((node){to[i],dis[to[i]]});
			}
		}
	}
}
int main(){
	int T; scanf("%d",&T);
	while(T--){
		memset(hd,0xff,sizeof(hd));
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++){
			scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].l,&e[i].a);
			add(e[i].u,e[i].v,e[i].l),add(e[i].v,e[i].u,e[i].l);
		}
		dij(1);
		for(int i=1;i<=n;i++) fa[i]=i;
		scanf("%d%d%d",&q,&k,&s);
		if(k!=0) return 1;
		for(int i=1;i<=q;i++)
			scanf("%d%d",&qu[i].v,&qu[i].p),qu[i].i=i;
		std::sort(e+1,e+1+m,cmp1);
		std::sort(qu+1,qu+1+q,cmp2);
		for(int i=1,j=1;i<=q;i++){
			while(j<=m&&e[j].a>qu[i].p) uni(e[j].u,e[j].v),++j;
			qu[i].a=dis[gfa(qu[i].v)];
		}
		std::sort(qu+1,qu+1+q,cmp3);
		for(int i=1;i<=q;i++)
			printf("%d\n",qu[i].a);
	}
	return 0;
}

评测结果