1 人解决，1 人已尝试。
1 份提交通过，共有 11 份提交。
9.4 EMB 奖励。
单点时限: 3.0 sec
内存限制: 256 MB
A Captain of pirates Jack Swallow was looking for legendary coin of Azteca once belonging to explorer Hernando Cortez, and finally he found the island with the coin. He made a plan to get it, however, one of his subordinates Hector Barbarossa betrayed Jack and usurped his ship the Black Perl, the fastest ship in the world, and the legendary coin of Azteca. And then, long time passed.
Eliza, a beautiful daughter of Governor of Royal Port Town at Mediterranean, is still keeping Willy Turner, Jr.’s White Ruby. Young Eliza and her father had saved young Willy from a drift on the sea. And now, Willy is a blacksmith’s apprentice and self-taught expert swordsman. Willy and Eliza loves each other, but cannot tell about it because of their birth.
One night of the new moon, captain Barbarossa with the Black Perl and his subordinates attacked to Royal Port Town and kidnapped Eliza to remove a curse. Captain Barbarossa and his subordinates were cursed by the legendary coin of Azteca and turned into immortal zombie. Zombie is weak to light from the sun. Therefore, they can go out from a cave only at night of the new moon, and at three nights before and after night of the new moon. You can assume that the mean time between new moons is twenty nine days. To remove the curse, they should have a ritual sacrifice on time 0 of night of the new moon at the island that once the legendary coin of Aztaca is there. Moreover, ritually killed person should be a person with the White Ruby. Captain Barbarossa is going to kill Eliza to remove the curse. Jack was at Royal Port Town by chance. Jack told about the ritual sacrifice to her father because it was a golden opportunity to avenge for Barbarossa and to get back his ship. Her father promised to give a large amount of treasures to Jack for a reward of getting back Eliza. He also promised to permit Willy the marriage to Eliza for a reward of accompany with Jack and getting back Eliza because he did not trust him completely.
It is impossible to catch up with the Black Perl because the ship is the fastest ship in the world. But captain Barbarossa and his subordinates cannot sail except for nights that they can live. In addition, Jack knows how to beat off zombies. Therefore, it is possible to save Eliza if Jack and Willy reach to the island until the time to start the ritual sacrifice.
Captain Barbarossa needs to sail t unit time to reach to the island. In addition, his subordinates who do not accompany to him prepare the ritual sacrifice. Therefore, the ritual sacrifice start at once as soon as the conditions are satisfied. On the other hand, the current Jack’s ship the Golden Python is a fast ship, but they cannot sail more than s unit time without supplying the ship with foods, water, and so on. They can supply the ship at any port town. What is more, you can consider the time for supply as 0 because Jack is a specialist of supply. You can assume that 1 day consists of 24 unit time. You can also assume that the sun rises at time 5 and the sunset is at time 19, and the moon is on the sky from time 19 till time 5 of the next day.
Your job is to write a program to check whether Jack and Willy are possible to save Eliza. You can assume that Captain Barbarossa starts sailing from Royal Port Town to the island at time 0 of the night of new moon, and Jack and Willy start sailing r unit time after Captain Barbarossa’s departure.
Input consists of multiple test cases. The first line of each test case contains five positive integers n ( n <= 1,000 ), m (m < 20,000), t (t < 1,000,000), s (s < 10,000) and r (r < 128), separated by single space character. The integer n indicates the number of ports. Each port and the island has different ID. ID should be a non-negative integer less than or equal to n. 0 is assigned for the island, and 1 is assigned Royal Port. Others are assigned to other ports respectively. The following m lines contain 3 integers a , b ( 0 <= a ,b <= n , a != b) and c ( 0 < c <= s) separated by single space. These integers indicate information about a route, c unit time required to sail from a to b . Input is terminated by a case of n = m = t = s = r = 0, and it should not be processed.
You can assume that Jack and Willy can reach to the island.
For each test case, you should output “Yes” if it is possible to save Eliza, otherwise output “No”.
2 2 25 20 5 1 2 20 2 0 20 2 2 25 1000 5 1 2 1000 2 0 1000 0 0 0 0 0
Yes No
1 人解决，1 人已尝试。
1 份提交通过，共有 11 份提交。
9.4 EMB 奖励。