链接

好题，先放这。

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define NN N<<1
#define PII pair<int,int>
using namespace std;

const int N=4e5+10;

int n,m,s;
int e[NN],h[N],w[NN],ne[NN],hd[N],cnt,cnt1;
int c[N],nr[N],ans[N];
int f[N],k;
struct node{
    int l,r,v;
    int id;
}b[N],q[N];
bool v[N];
int d[N];
void add(int x,int y,int z){
    e[++cnt]=y;
    hd[cnt]=x;
    w[cnt]=z;
    ne[cnt]=h[x];
    h[x]=cnt;
}

void dij(){
    priority_queue<PII,vector<PII>,greater<PII> >q;
    for(int i=1;i<=s;i++){
        d[c[i]]=0;
        q.push({0,c[i]});
        nr[c[i]]=c[i];
    }
    while(q.size()){
        int pos=q.top().second;
        q.pop();
        if(v[pos]) continue;
        v[pos]=1;
        for(int i=h[pos];i;i=ne[i]){
            int j=e[i];
            if(d[j]>d[pos]+w[i]){
                d[j]=d[pos]+w[i];
                nr[j]=nr[pos];
                if(!v[j]) q.push({d[j],j});
            }
        }
    }
}
bool cmp(node a,node b){
    return a.v<b.v;
}

int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    memset(d,0x3f,sizeof d);
    cin>>n>>s>>m;
    for(int i=1;i<=s;i++){
        cin>>c[i];
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    cin>>k;
    for(int i=1;i<=k;i++){
        int x,y,z;
        cin>>x>>y>>z;
        q[i].l=x;
        q[i].r=y;
        q[i].v=z;
        q[i].id=i;
    }
    dij();
    for(int i=1;i<=cnt;i+=2){
        int u=hd[i],v=e[i];
        if(nr[u]!=nr[v]) b[++cnt1]={nr[u],nr[v],d[u]+d[v]+w[i],0};
    }
    for(int i=1;i<=n;i++) f[i]=i;
    sort(b+1,b+1+cnt1,cmp);
    sort(q+1,q+1+k,cmp);
    for(int i=1,j=1;i<=k;i++){
        while(j<=cnt1&&b[j].v<=q[i].v){
            int u=find(b[j].l),v=find(b[j].r);
            if(u!=v) f[u]=v;
            j++;
        }
        ans[q[i].id]=(find(q[i].l)==find(q[i].r));
    }
    for(int i=1;i<=k;i++){
        cout<<(ans[i]?"TAK\n":"NIE\n");
    }
}