编程介的小学生 2017-02-15 15:23 采纳率: 20.5%
浏览 803
已采纳

Help John!

John is 7 years old and he lives in Faegfalch, which is a very dangerous city, so John must go to school according to the path his mother told him. This way isn't the fastest way from John's home to school. John is a very lazy boy and he doesn't like walking, so he is searching for the fastest way from home to school. He only has to make sure, that his mother can not see from her flat window that he is going on another way (he must pass the first crossroad where mother told him to go across, and never walk back home unless he comes back from school).

INPUT

First line of input includes t (1<=t<=77) - the number of test cases.

First line of every test includes n (1<=n<=1 000) - the number of crossroads in Faegfalch and m (1<=m<=30 000) - the number of roads. In next m lines there are descriptions of roads. Every road description includes three numbers: a, b (1<=a, b<=n) - crossroads, where the road starts and ends and c (1<=c<=1 000) - the time needed to walk by this street (John can't walk faster, because if he did it, he would be cought by Faegnad (football team) fans and he can't go slower, because he doesn't want to be late and he wants to talk with his friends and make some homework before lessons start). In next line there is an integer k (1<=k<=m) - the number of crossroads, which his mother told him to meet. Next line includes k crossroads which he has to meet.

The boy's home is always at location 1 and the school positions at location n. All the paths are bidirectional.

OUTPUT

Output has one line for every test, which include word "TEST" and then the order number. Print the character "Y" if John can go to his school from home, and the time needs to go to school by roads which his mother told him to go, subtracts the minimal time which he needs to walk to school that can not be seen by his mother. Output only an "N" if there is no way to his school.

SAMPLE

INPUT

2
6 10
1 2 2
1 3 2
1 6 1
2 6 4
2 3 3
2 4 1
3 4 5
4 5 1
4 6 3
5 6 2
6
1 2 3 4 5 6
3 1
1 2 1
3
1 2 3

(Explanation for the first sample. the way his mother told him is 1->2->3->4->5->6, with a total length of 13. And the shortest path he can find is 1->2->6, with a total length of 6. So the final output is 13 - 6 = 7.)

OUTPUT

TEST 1 Y 7
TEST 2 N

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-02-20 17:17
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥20 iqoo11 如何下载安装工程模式
  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?