Skip to content

1198: 加油

题目

题目描述

给定一个$n$个点、$m$条边的带权无向图,其中有$s$个点是加油站。

每辆车都有一个油量上限$b$,即每次行走距离不能超过$b$,但在加油站可以补满。

$q$次询问,每次给出$x,y,b$,表示出发点是$x$,终点是$y$,油量上限为$b$,且保证$x$点和$y$点都是加油站,请回答能否从$x$走到$y$。

输入格式

第一行包含三个正整数$n,s,m$,表示点数、加油站数和边数。

第二行包含$s$个互不相同的正整数$c[1],c[2],...c[s]$,表示每个加油站。

接下来$m$行,每行三个正整数$u[i],v[i],d[i]$,表示$u[i]$和$v[i]$之间有一条长度为$d[i]$的双向边。

接下来一行包含一个正整数$q$,表示询问数。

接下来$q$行,每行包含三个正整数$x[i],y[i],b[i]$,表示一个询问。

输出格式

输出$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

数据范围

$2\le s\le n \le 200000,1\le m,q\le 200000,$

$1\le c[i],u[i],v[i]\le n,u[i]\ne v[i],1\le d[i]\le 10000,$

$ 1\le x[i],y[i]\le n,x[i]\ne y[i],1\le b[i]\le 2*10^9$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!