Description：

$n$ 个点 $m$ 条边的带权无向图， $s$ 个点是加油站。 $q$ 次询问出发点是 $x$ ，终点是 $y$ ，油量上限为 $b$ ，保证 $x$ 和 $y$ 都是加油站，请回答能否从 $x$ 走到 $y$ 。

$1\leqslant n\leqslant 2\times 10^5$

Solution：

发现实际上只有加油站这些关键点之间的距离是有用的，于是先跑一遍多源 $dijkstra$ 预处理出每个点最近的加油站和到它的距离，然后连边 $(c[x],c[y],d[x]+d[y]+v(x,y))$ ，然后求出关键点之间的最小生成树，然后就可以倍增求链上最小值了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,s,m,p;

#define MAXN 200010

int c[MAXN];

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

	return;

}

int d[MAXN],pos[MAXN];

bool vis[MAXN];

struct edges

{

	int u,v,w;

}es[MAXN];

int edgesnum = 0;

void addedges(int a,int b,int c)

{

	es[++edgesnum] = (edges){a,b,c};

	return;

}

int f[MAXN];

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

bool cmp_w(edges a,edges b){return a.w < b.w;}

int g[MAXN][18],h[MAXN][18];

int dep[MAXN];

int ins[MAXN],scc = 0;

void dfs(int k,int depth)

{

	ins[k] = scc;

	dep[k] = depth;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == h[k][0])continue;

		h[e[i].to][0] = k;

		g[e[i].to][0] = e[i].v;

		dfs(e[i].to,depth + 1);

	}

	return;

}

int query(int a,int b)

{

	int res = 0;

	if(dep[a] < dep[b])swap(a,b);

	for(int k = 17;k >= 0;--k)

	{

		if(dep[h[a][k]] >= dep[b])

		{

			res = max(res,g[a][k]);

			a = h[a][k];

		}

	}

	if(a == b)return res;

	for(int k = 17;k >= 0;--k)

	{

		if(h[a][k] != h[b][k])

		{

			res = max(res,max(g[a][k],g[b][k]));

			a = h[a][k];b = h[b][k];

		}

	}

	res = max(res,max(g[a][0],g[b][0]));

	return res;

}

int main()

{

	scanf("%d%d%d",&n,&s,&m);

	for(int i = 1;i <= s;++i)scanf("%d",&c[i]);

	int a,b,v;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&v);

		add(a,b,v);

	}

	priority_queue< pair<int,int> > q;

	memset(d,0x3f,sizeof(d));

	for(int i = 1;i <= s;++i)

	{

		q.push(make_pair(0,c[i]));

		d[c[i]] = 0;pos[c[i]] = c[i];

	}

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(vis[k])continue;

		vis[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				pos[e[i].to] = pos[k];

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	for(int i = 1;i <= edgenum;i += 2)

	{

		addedges(pos[e[i].to],pos[e[i + 1].to],d[e[i].to] + d[e[i + 1].to] + e[i].v);

	}

	sort(es + 1,es + 1 + m,cmp_w);

	edgenum = 0;

	memset(lin,0,sizeof(lin));

	for(int i = 1;i <= n;++i)f[i] = i;

	for(int i = 1;i <= m;++i)

	{

		int p = find(es[i].u),q = find(es[i].v);

		if(p == q)continue;

		f[p] = q;

		add(p,q,es[i].w);

	}

	memset(vis,false,sizeof(vis));

	for(int i = 1;i <= s;++i)

	{

		if(ins[c[i]] == 0)

		{

			++scc;

			dfs(c[i],1);

		}

	}

	for(int k = 1;k <= 17;++k)

	{

		for(int i = 1;i <= s;++i)

		{

			int p = c[i];

			h[p][k] = h[h[p][k - 1]][k - 1];

			g[p][k] = max(g[p][k - 1],g[h[p][k - 1]][k - 1]);

		}

	}

	scanf("%d",&p);

	for(int i = 1;i <= p;++i)

	{

		scanf("%d%d%d",&a,&b,&v);

		if(ins[a] != ins[b])puts("NIE");

		else if(query(a,b) <= v)puts("TAK");

		else puts("NIE");

	}

	return 0;

}