代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2e5+7,MAXQ=1e5+8;

int n,m,Q,K,S;
int dis[MAXN];
bool vis[MAXN];

typedef pair<int,int> pii;
struct edge{int to,l,h;};
vector <edge> a[MAXN];
vector <edge> aa;
priority_queue <pii> q;

void spfa(){
	memset(dis,63,sizeof(dis));
	q.push(make_pair<int,int>(dis[1]=0,1));
	while (!q.empty()){
		int u=q.top().second; q.pop();
		if (vis[u]) continue; vis[u]=1;
		for (int i=0;i<a[u].size();i++){
			int v=a[u][i].to,d=dis[u]+a[u][i].l;
			if (dis[v]>d) q.push(make_pair<int,int>(-(dis[v]=d),v));
		}
	}
}

struct Query{
	int id,s,h,ans;
	void read(){scanf("%d%d",&s,&h);}
}qs[MAXQ];
bool cmp(Query x,Query y){return x.h>y.h;}
bool cmp_id(Query x,Query y){return x.id<y.id;}
bool cmp_he(edge x,edge y){return x.h>y.h;}

int fa[10005];
int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
void Union(int x,int y){x=Find(x),y=Find(y);if(x!=y){dis[x]<dis[y]?fa[y]=x:fa[x]=y;}}
bool Same(int x,int y){return Find(x)==Find(y);}

void solve(){
//	for (int i=1;i<=n;i++) printf("%d%c",dis[i]," \n"[i==n]);
	scanf("%d%d%d",&Q,&K,&S);
	for (int i=1;i<=n;i++) fa[i]=i;
	for (int i=1;i<=Q;i++) qs[i].id=i,qs[i].read();
	sort(qs+1,qs+Q+1,cmp);
	sort(aa.begin(),aa.end(),cmp_he);
	int now=0;
	for(int i=1;i<=Q;i++){
		while(now<m&&aa[now].h>qs[i].h) Union(aa[now].to,aa[now].l),now++;
		qs[i].ans=dis[Find(qs[i].s)];
	}
	sort(qs+1,qs+Q+1,cmp_id);
	for (int i=1;i<=Q;i++) printf("%d\n",qs[i].ans);
}

int T;
int main(){
	scanf("%d",&T);
	while (T--){
		for (int i=1;i<=n;i++) a[i].clear();
		scanf("%d%d",&n,&m);
		for (int i=1;i<=m;i++){
			int u,v,l,h;
			scanf("%d%d%d%d",&u,&v,&l,&h);
			a[u].push_back((edge){v,l,h});
			a[v].push_back((edge){u,l,h});
			aa.push_back((edge){u,v,h});
		}
		spfa();
		solve();
	}
	return 0;
}

评测结果