好题,先放这。
#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");
}
}