wa on #2 求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=2e9;
int read(){
	int x=0;
	char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+(c-'0'),c=getchar();
	return x;
}
int t,n,m,q1,x,y,z,ww,a[500005],b[500005];
int ver[1000005],ne[1000005],head[500005],w[1000005],p[1000005],tot;
void add(int x,int y,int z,int ww){
	ver[++tot]=y,ne[tot]=head[x],w[tot]=z,p[tot]=ww,head[x]=tot;
}
struct pai{
	int k,x;
	bool operator <(const pai &b) const{
		if(k!=b.k) return k<b.k;
		else return x>b.x;
	}
}f[400005];
int rot[500005],top,ls[400005],rs[400005];
void build(int root,int l,int r){
	if(l==r){ f[root]={inf,-1},ls[root]=rs[root]=0; }
	int mid=(l+r)>>1;
	if(ls[root]) build(ls[root],l,mid);
	if(rs[root]) build(rs[root],mid+1,r);
	f[root]={inf,-1},ls[root]=rs[root]=0;
}
void update(int root,int l,int r,int k,int x){
	if(l==r){ f[root]={k,x};return; }
	int mid=(l+r)>>1;
	if(k<=mid){
		if(!ls[root]) ls[root]=++top;
		update(ls[root],l,mid,k,x);
	}
	else{
		if(!rs[root]) rs[root]=++top;
		update(rs[root],mid+1,r,k,x);
	}
	if(f[ls[root]].x>=f[rs[root]].x) f[root]=f[ls[root]];
	else f[root]=f[rs[root]];
}
pai Find(int root,int l,int r,int fl,int k){
	if(l>r||!root||f[root].x<k) return {q1+1,-1};
	if(l==r) return f[root];
	int mid=(l+r)>>1;
	if(fl>mid) return Find(rs[root],mid+1,r,fl,k);
	pai x=Find(ls[root],l,mid,fl,k);
	if(x.x>=k) return x;
	return Find(rs[root],mid+1,r,fl,k);
}
struct node{
	int k;
	pai x;
	bool operator <(const node &b) const{
		return b.x<x;
	}
};priority_queue<node> q;
pai d[500005];
bool flag[500005];
void dij(){
	for(int i=1;i<=n;i++) flag[i]=0;
	for(int i=1;i<=n;i++) d[i]={q1+1,-1};
	d[1]={1,b[1]},q.push({1,d[1]});
	while(!q.empty()){
		int x=q.top().k;q.pop();
		if(flag[x]) continue;
		flag[x]=1;
		for(int i=head[x];~i;i=ne[i]){
			if(flag[ver[i]]) continue;
			pai xx={q1+1,-1};
			if(p[i]==a[d[x].k]&&w[i]<=d[x].x){
				xx={d[x].k,d[x].x-w[i]};
			}
			else{
				xx=Find(rot[p[i]],1,q1,d[x].k+1,w[i]);
				if(xx.x<w[i]) continue;
				xx={xx.k,xx.x-w[i]};
			}
			if(xx<d[ver[i]]) d[ver[i]]=xx,q.push({ver[i],d[ver[i]]});
		}
	}
}
signed main(){
	f[0]={inf,-1};
	t=read();
	while(t--){
		n=read(),m=read(),q1=read();
		tot=top=0;
		for(int i=1;i<=n;i++) head[i]=-1;
		for(int i=1;i<=m;i++) rot[i]=++top;
		for(int i=1;i<=m;i++){
			x=read(),y=read(),ww=read(),z=read();
			add(x,y,z,ww),add(y,x,z,ww);
		}
		for(int i=1;i<=q1;i++) a[i]=read(),b[i]=read();
		for(int i=1;i<=q1;i++) update(rot[a[i]],1,q1,i,b[i]);
		dij();
		for(int i=1;i<=n;i++){
			if(d[i].k<=q1) printf("1");
			else printf("0");
		}
		printf("\n");
		for(int i=1;i<=m;i++) build(rot[i],1,q1);
	}
	return 0;
}