代码

// finally 65 points?
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2e5+6,MAXQ=4e5+7;

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[MAXN];
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(){
    scanf("%d%d%d",&Q,&K,&S);
    if (K==1) exit(0);
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=1;i<=Q;i++) qs[i].id=i,qs[i].read(),qs[i].ans=-1;
    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(); aa.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});
        }
        memset(vis,0,sizeof(vis));
        spfa();
        solve();
    }
    return 0;
}

评测结果