Problem2939--烈火英雄冲冲冲

2939: 烈火英雄冲冲冲

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 14  Solved: 4
[Submit] [Status] [Web Board] [Creator:]

Description

相信大家都爱过烈火英雄吧,南昌比赛刚刚做完消防队比拼,现在我们再来一道消防队问题。
现在有n个站点,m条带权路径(无向),其中n个站点中有x个是作为加水站,因为现在城市已经燃起了大火,
消防车必须要有水才能通过道路,加水站可以为消防车加满水
现在李达康书记为了更好地了解火情,每次会问你st、en、b
代表出发点是st,终点是en,存储水容量为b的消防车能不能从st到达en点。保证两个点都是加水站

Input

第一行包括三个整数n,x,m 表示站点个数和加水站个数以及路径数(2 <= x <= n <= 2e5  , 1 <= m <= 2e5)
接下来一行包含x个数,表示为每个加油水的节点 (1 <= a[i] <= n)
再然后m行,每一行输入u,v,c 表示从u和v之间的一条路径需要花费c的水量(1 <= u,v <= n  ,  1 <= c <= 1e4)
接下来输入一个查询个数q(1 <= q <= 2e5)
最后q行,每一行输入st,en,b 表示要查询的起终点和消防车的存水量 (1 <= st , en <= n  && st != en    ,     1 <= b <= 2e9)

Output

每组查询对应输出一行,如果可以安全到达则输出TAK,否则输出NIE

Sample Input Copy

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 Copy

TAK
TAK
TAK
NIE