最小生成树+最短路+并查集维护
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+100,M=N*2;
int n,m,s;
int h[N],e[M],ne[M],w[M],idx;
int dis[N],pos[N];
bool vis[N];
int f[N];
int a[N];
bool ans[N];
int q;
struct NODE{
int x,y,z;
}E[N*2];
struct node{
int x,y,z;
bool operator <(const node &z)const{
return x>z.x;
}
};
struct ASK{
int x,y,b,id;
}que[N];
int find(int x)
{
if(f[x]==x)return x;
else return f[x]=find(f[x]);
}
void merge(int x,int y)
{
int s1=find(x),s2=find(y);
if(s1==s2) return;
f[s1]=s2;
}
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void Dijkstra()
{
priority_queue<node> q;
memset(dis,0x3f,sizeof dis);
for(int i=1;i<=s;i++)
{
dis[a[i]]=0;
pos[a[i]]=a[i];
q.push({0,a[i],a[i]});
}
while(q.size())
{
int t=q.top().y,fr=q.top().z;
q.pop();
if(vis[t]) continue;
vis[t]=true;
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(dis[j]>dis[t]+w[i])
{
pos[j]=fr;
dis[j]=dis[t]+w[i];
if(!vis[j])
q.push({dis[j],j,fr});
}
}
}
}
signed main()
{
memset(h,-1,sizeof h);
cin>>n>>s>>m;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=s;i++) cin>>a[i];
for(int i=1;i<=m;i++)
{
int u,v,z;
cin>>u>>v>>z;
E[i]={u,v,z};
add(u,v,z),add(v,u,z);
}
Dijkstra();
cin>>q;
for(int i=1;i<=q;i++)
{
int x,y,z;
cin>>x>>y>>z;
que[i]={x,y,z,i};
}
sort(que+1,que+q+1,[&](ASK a,ASK b){
return a.b<b.b;
});
for(int i=1;i<=m;i++)
{
int x=E[i].x,y=E[i].y,z=E[i].z;
z+=dis[x]+dis[y];
x=pos[x],y=pos[y];
if(x==y) continue;
E[i]={x,y,z};
}
sort(E+1,E+m+1,[&](NODE a,NODE b){
return a.z<b.z;
});
int j=1;
for(int i=1;i<=q;i++)
{
for(;j<=m&&E[j].z<=que[i].b;j++) merge(E[j].x,E[j].y);
int s1=find(que[i].x),s2=find(que[i].y);
if(s1==s2) ans[que[i].id]=true;
else ans[que[i].id]=false;
}
for(int i=1;i<=q;i++)
if(ans[i])puts("TAK");
else puts("NIE");
return 0;
}