UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4144. [AMPPZ2014]Petrol

统计 下载数据

Description

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

Input

第一行包含三个正整数n,s,m(2<=s<=n<=200000,1<=m<=200000),表示点数、加油站数和边数。
第二行包含s个互不相同的正整数c[1],c[2],...c[s](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),表示一个询问。

Output

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

Sample Input

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

Sample Output

TAK
TAK
TAK
NIE

Hint

Source

鸣谢Claris上传