代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N = 4e5 + 10, M = 8e5 + 10; //开大！！！ 
int T;
int n,m,final[N],nex[M];
struct edge{
	int x,y,len,hi;
	bool operator < (const edge & e) const {
		return hi < e.hi || hi == e.hi && len > e.len;
	}
} e[M], es[M];

char c;
void read(int &x) {
	while ((c=getchar()) > '9' || c < '0');
	x = c - '0';
	while ((c=getchar()) >= '0' && c <= '9') x = x * 10 + c - '0';
}

int lastans;
int dis[N];
set<pair<int,int> > he;

void dij() {
	memset(dis, 127, sizeof dis); dis[1] = 0;
	he.clear();
	he.insert(make_pair(0, 1));
	while (!he.empty()) {
		int x = (*he.begin()).second;
		he.erase(he.begin());
		for (int i = final[x]; i; i=nex[i]) {
			int y = e[i].y;
			if (dis[x] + e[i].len < dis[y]) {
				if (dis[y] != dis[0]) he.erase(make_pair(dis[y], y));
				dis[y] = dis[x] + e[i].len;
				he.insert(make_pair(dis[y], y));
			}
		}
	}
}

int Q,K,S;
int ans[N],mi[N],fa[N];

int gf(int x) {
	return fa[x] == 0 ? x : fa[x] = gf(fa[x]);
}

void merge(int x,int y) {
	x = gf(x), y = gf(y);
	if (x != y) {
		fa[x] = y;
		mi[y] = min(mi[y], mi[x]);
	}
}

int main() { 
	for (cin>>T; T; T--) {
		memset(final,0,sizeof final);
		memset(e,0,sizeof e);
		memset(nex,0,sizeof nex);
		cin>>n>>m;
		for (int i = 1; i <= m; i++) {
			read(e[i].x),read(e[i].y),read(e[i].len),read(e[i].hi);
			es[i] = e[i + m] = e[i];
			swap(e[i + m].x, e[i + m].y);
		}
		sort(e + 1, e + 1 + m * 2);
		for (int i = 1; i <= m * 2; i++) {
			nex[i] = final[e[i].x];
			final[e[i].x] = i;
		}
		
		dij();
		memset(fa,0,sizeof fa);
		for (int i = 1; i <= n; i++) mi[i] = dis[i];
		
		cin>>Q>>K>>S;
		for (int z = 1; z <= Q; z++) {
			int v,p; read(v),read(p);
			es[m + z].x = v, es[m + z].y = z, es[m + z].hi = p;
			es[m + z].len = -1;
		}
		
		sort(es + 1,es + 1 + m + Q);
		for (int i = m + Q; i; i--) {
			if (es[i].len > 0) {
				merge(es[i].x,es[i].y);
			} else {
				ans[es[i].y] = mi[gf(es[i].x)];
			}
		}
		
		for (int i = 1; i <= Q; i++) {
			printf("%d\n",ans[i]);
		}
	}
}

评测结果