代码

#include<bits/stdc++.h>
using namespace std;
inline void read(int &x){
    char c = getchar();
    int p = 1;
    x = 0;
    while(!isdigit(c)){
        if(c == '-')p = -1;
        c = getchar();
    }
    while(isdigit(c)){
        x = (x << 1) + (x << 3) + (c ^ '0');
        c = getchar();
    }
    x *= p;
}
const int maxn = 400050;
int head[maxn], f[maxn], tot, cnt, n, m, q, k, s, T;
long long dis[maxn], dist[maxn], ans[maxn];
bool vis[maxn];
inline void pre(){
    for(register int i = 0; i <= n + 1; ++i){
        f[i] = i;
    }
}
inline int getf(int u){
    if(u==f[u])return u;
    f[u]=getf(f[u]);
    dis[f[u]]=min(dis[f[u]],dist[u]);
    return f[u];
}
inline void merg(int u,int v){
    int x = getf(v), y = getf(u);
    if(x ^ y)f[x] = y, dis[y]=min(dis[y],dis[x]);
}
struct edge{
    int to, next, w;
}e[maxn << 1];
struct ed{
    int u, v, a;
}e1[maxn << 1];
struct node{
    int v, p, t;
}ask[maxn << 1];
inline void add(int u, int v, int w){
    e[++tot].to = v;
    e[tot].next = head[u];
    e[tot].w = w;
    head[u] = tot;
}
/*inline void spfa(){
    deque<int>qu;
    qu.push_back(1);
    vis[1] = 1;
    memset(dist, 0x3f, sizeof(dist));
    dist[1]=0;
    while(!qu.empty()){
        cerr<<"!!!"<<endl;
        int u=qu.front();
        qu.pop_front();
        vis[u]=0;
        for(register int i=head[u];i;i=e[i].next){
            if(e[i].w+dist[u]<dist[e[i].to]){
                dist[e[i].to]=e[i].w+dist[u];
                if(!vis[e[i].to]){
                    if(dist[e[i].to]>dist[qu.front()])qu.push_front(e[i].to);
                    else qu.push_back(e[i].to);
                    vis[e[i].to]=1;
                }
            }
        }
    }
}*/
/*queue<int>qu;
inline void spfa(){
    while(!qu.empty())qu.pop();
    dist[1]=0;
    qu.push(1);
    while(!qu.empty()){
        int u=qu.front();
        cerr<<u<<endl;
        qu.pop();
        vis[u]=0;
        for(register int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dist[u]+e[i].w<dist[v]){
                dist[v]=dist[u]+e[i].w;
                if(!vis[v]){
                    vis[v]=1;
                    qu.push(v);
                }
            }
        }
    }
    }*/
#define pi pair<int, int>
#define mp make_pair
#define fi first
#define se second
inline void dijkstra(){
    priority_queue<pi,vector<pi >,greater<pi > >q;
    for(register int i = 1; i <= n; ++i){
        dist[i] = LONG_LONG_MAX / 3;
    }
    dist[1]=0,q.push(mp(0,1));
    int u;pi x;
    while(!q.empty()){
        x=q.top(),q.pop();
        u=x.se;
        if(!vis[u]){
            vis[u]=1;
            for(register int i=head[u],v=e[i].to;i;i=e[i].next,v=e[i].to){
                if(dist[v]>x.fi+e[i].w){
                    dist[v]=x.fi+e[i].w;
                    q.push(mp(dist[v],v));
                }
            }
        }
    }
}
inline bool cmp1(ed a, ed b){
    return a.a > b.a;
}
inline bool cmp2(node a, node b){
    return a.p > b.p;
}
int main(){
    read(T);
    while(T--){
        //cerr<<"!"<<endl;
        read(n), read(m);
        int u, v, w, a, p, pos;
        pre();
        cnt = 0, tot = 0, pos = 1;
        memset(head, 0, sizeof(head));
        memset(vis, 0, sizeof(vis));
        for(register int i = 1; i <= m; ++i){
            //cerr<<i<<endl;
            read(u), read(v), read(w), read(a);
            add(u, v, w), add(v, u, w);
            e1[++cnt].u = u, e1[cnt].v = v, e1[cnt].a = a;
        }
        read(q), read(k), read(s);
        for(register int i = 1; i <= q; ++i){
            //cerr<<i<<endl;
            read(v), read(p);
            ask[i].v = v, ask[i].p = p, ask[i].t = i;
        }
        dijkstra();
        for(register int i = 1; i <= n; ++i){
            dis[i] = dist[i];
        }
        //cerr<<dist[2]<<endl;
        sort(e1 + 1, e1 + 1 + m, cmp1);
        e1[m + 1].a = 0;
        sort(ask + 1, ask + 1 + q, cmp2);
        //cerr<<"!!!"<<endl;
        for(register int i = 1; i <= q; ++i){
            //cerr<<i<<' '<<pos<<endl;
            while(e1[pos].a > ask[i].p){
                if(pos > m)break;
                int u = e1[pos].u, v = e1[pos].v;
                merg(u, v);
                //cout<<dist[getf(u)]<<' '<<dist[u]<<' '<<dist[v]<<endl;
                //dis[getf(u)] = min(dist[getf(u)], min(dist[u], dist[v]));
                pos++;
            }
            //cout<<ask[i].v<<endl;
            ans[ask[i].t] = dis[getf(ask[i].v)];
        }
        //cout<<dist[30]<<endl;
        for(register int i = 1; i <= q; ++i){
            printf("%lld\n", ans[i]);
        }
    }
    return 0;
}

评测结果