8144: BZOJ4144：[AMPPZ2014]Petrol

给定一个n个点、m条边的带权无向图，其中有s个点是加油站。 每辆车都有一个油量上限b，即每次行走距离不能超过b，但在加油站可以补满。 q次询问，每次给出x,y,b，表示出发点是x，终点是y，油量上限为b，且保证x点和y点都是加油站，请回答能否从x走到y。

输入格式

第一行包含三个正整数n,s,m(2<=s<=n<=200000,1<=m<=200000)，表示点数、加油站数和边数。 第二行包含s个互不相同的正整数c[1],c[2],...c(1<=c[i]<=n)，表示每个加油站。 接下来m行，每行三个正整数u[i],v[i],d[i](1<=u[i],v[i]<=n,u[i]!=v[i],1<=d[i]<=10000)，表示u[i]和v[i]之间有一条长度为d[i]的双向边。 接下来一行包含一个正整数q(1<=q<=200000)，表示询问数。 接下来q行，每行包含三个正整数x[i],y[i],b[i](1<=x[i],y[i]<=n,x[i]!=y[i],1<=b[i]<=2*10^9)，表示一个询问。

输出格式

输出q行。第i行输出第i个询问的答案，如果可行，则输出TAK，否则输出NIE。

样例输入

6 4 5
1 5 2 6
1 3 1
2 3 2
3 4 3
4 5 5
6 4 5
4
1 2 4
2 6 9
1 5 9
6 5 8

样例输出

TAK
TAK
TAK
NIE

提示

没有写明提示

题目来源

鸣谢Claris上传