Submit solution

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 256M

Authors:
Problem type
Allowed languages
C, C++

Rar the Cat and his friend go home together on taxi after a party. Rar the Cat lives in a town that can be modelled by a graph with V nodes and E bidirectional weighted edges. The party takes place at node P, Rar the Cat's friend lives at node D and Rar the Cat lives at node R. Rar the Cat decides to send his friend home before going home himself, of course offering to pay for the trip. Below are the fares:

  • Flag-down (fixed cost): $3
  • Each kilometre for the first 10 kilometres: $2
  • Each kilometre after 10 kilometres: $1

Find the minimum cost required to do so, or state that it is impossible.

Input Format

The first line of input will contain five integers V, E, P, D, R.

The following E lines will contain three integers A, B, C on each line, representing an edge connecting two nodes A and B with weight C.

Output Format

If it is not possible for Rar the Cat to send his friend home and then return home, output Nooooooooo!!!.

If it is possible for Rar the Cat to send his friend home but not possible for him to return home, output the minimum cost required to send his friend home on one line, then output Yippee!!! on the next line as he would have an excuse to not go home and stay overnight at his friend's place.

If it is possible for Rar the Cat to send his friend home and then return home, output the minimum cost required.

Constraints

Subtask 1 (100%): 1 \le V, C \le 100\,000. 1 \le E \le 300\,000. 0 \le A, B, P, D, R < V.

Subtask 2 (0%): Sample Testcases.

Sample

Input
5 4 0 2 2
0 1 1
1 2 1
2 3 1
3 4 1
Output
7
Input
5 1 0 1 2
0 1 5
Output
13
Yippee!!!
Input
3 1 0 2 1
0 1 1
Output
Nooooooooo!!!

Comments

There are no comments at the moment.