代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <queue>
#include <fstream>
using namespace std;
long long int cnt,h[10000005][2],tag[10000005],t,n,m,map[10000005][3],start[1000005],road[10000005][4],minroad[1000005];
int dijk()
{
	h[1][0]=1;
	h[1][1]=0;
	for(int i=1;i<=n;i++)tag[i]=0;
	int p=1;
	for(int i=1;i<=n;i++)minroad[i]=9999999999;
	minroad[1]=0;
	while(p>=1)
	{
		cnt++;
		
		int u=h[1][0];
		if(cnt%100000==0)
		{
			//cout<<cnt<<" "<<p<<" "<<u<<endl;
		}
		swap(h[1][0],h[p][0]);
		swap(h[1][1],h[p][1]);
		int x=1;
		//for(int i=1;i<=p;i++)cout<<h[i][0]<<" "<<h[i][1]<<"  ";
		p--;
		while(x<=p)
		{
			if(h[x][1]>h[x*2][1] && (h[x*2][1]<h[x*2+1][1] || x*2+1>p) && x*2<=p)
			{
				swap(h[x][0],h[x*2][0]);
				swap(h[x][1],h[x*2][1]);
				x=x*2;
			}
			else if(h[x][1]>h[x*2+1][1] && h[x*2+1][1]<h[x*2][1] && x*2+1<=p)
			{
				swap(h[x][0],h[x*2+1][0]);
				swap(h[x][1],h[x*2+1][1]);
				x=x*2+1;
			}
			else break;
		}
		
		//for(int i=1;i<=p;i++)cout<<h[i][0]<<" "<<h[i][1]<<"  ";
		//cout<<endl;
		
		int g=start[u];
		//cout<<u<<endl;
		while(g!=-1)
		{
			int now=map[g][0];
			//cout<<now<<endl;
			if(minroad[u]+map[g][1]<minroad[now])
			{
				minroad[now]=minroad[u]+map[g][1];
				if(tag[now]==0)
				{
					tag[now]=1;
					p++;
					h[p][0]=now;
					h[p][1]=minroad[now];
					x=p;
					while(x>0)
					{
						if(h[x][1]<h[x/2][1])
						{
							swap(h[x][0],h[x/2][0]);
							swap(h[x][1],h[x/2][1]);
							x=x/2;
						}
						else break;
					}
				}
			}
			g=map[g][2];
			
		}
		//cout<<endl;
		//for(int i=1;i<=n;i++)cout<<minroad[i]<<" ";
		//cout<<endl;
	}
}
int main(){
	ifstream fin("return.in");
	ofstream fout("return.out");
	fin>>t;
	while(t--)
	{
		fin>>n>>m;
		for(int i=1;i<=n;i++)start[i]=-1;
		for(int i=0;i<m;i++)
		{
			fin>>road[i][0]>>road[i][1]>>road[i][2]>>road[i][3];
			int x=road[i][0],y=road[i][1];
			map[i*2][0]=y;
			map[i*2][1]=road[i][2];
			map[i*2][2]=start[x];
			start[x]=i*2;
			map[i*2+1][0]=x;
			map[i*2+1][1]=road[i][2];
			map[i*2+1][2]=start[y];
			start[y]=i*2+1;
		}
		dijk();
		//for(int i=1;i<=n;i++)cout<<minroad[i]<<" ";
		long long int q,k,s;
		fin>>q>>k>>s;
		for(int i=1;i<=q;i++)
		{
			int v,p;
			fin>>v>>p;
			//cout<<v<<" "<<p<<endl;
			if(p>=road[1][3])fout<<minroad[v]<<endl;
			else fout<<"0"<<endl;
		}
	}
	return 0;
}

评测结果