Problem 1: Number Triples, (K Narayan Kumar, CMI)
In this problem you will be given a sequence of triples of positive integers. For example:
1 2 5 5 2 6 1 3 8 8 1 11 1 1 6 10 1 6 11 3 6 10 4 8 10 1 11
Given a pair of numbers A and B, a chain connecting A and B is a sequence of triples
A_{0} W_{0} A_{1}, A_{1} W_{1} A_{2}, A_{2} W_{2} A_{3}, ... A_{k-2} W_{k-2} A_{k-1}, A_{k-1} W_{k-1} A_{k}
such that
- A_{0} = A
- A_{k} = B
- For each i, 0 ≤ i < k, either the triple A_{i} W_{i} A_{i+1} or the triple A_{i+1} W_{i} A_{i} is in the given set of triples.
The value of such a chain is the sum of the W_{i}s in the chain. For example, here is a chain connecting 1 and 11 using the triples listed above:
1 1 6, 6 3 11
The value of this chain is 1+3 = 4.
Here is another chain connecting 1 and 11.
1 1 6, 6 1 10, 10 1 11
The value of this chain is 1+1+1 = 3. You can verify that among all chains connecting 1 and 11 this is the one with least value.
Sometimes there may be no chains connecting the given pair of numbers. For example, there is no chain connecting 1 and 2.
You will be given a sequence of triples and a pair of numbers. Your task is to find the value of the least value chain connecting the two numbers.
Input format
The first line of the input has three numbers M, A and B. M is the number of triples. The next M lines (lines 2,3,...,M+1) describe the triples. Line i+1 contains the three positive integers X_{i}, Y_{i} and Z_{i} that make up the ith triple. Your task is to find the value of the least value chain connecting A and B.
Output format
If there is at least one chain connecting A and B the first line of the output must consist of a single word YES. In that case the second line must contain a single integer value indicating the value of the least valued chain connecting A and B. If there are no chains connecting A and B the output should contain a single line with the word NO on it.
Test Data:
You may assume that 1 ≤ X_{i}, Y_{i}, Z_{i} ≤ 2000 and M ≤ 4000000.
Example:
We illustrate the input and output format using the above example:
Sample Input 1:
9 1 11 1 2 5 5 2 6 1 3 8 8 1 11 1 1 6 10 1 6 11 3 6 10 4 8 10 1 11
Sample Output 1:
YES 3
Sample Input 2:
9 1 2 1 2 5 5 2 6 1 3 8 8 1 11 1 1 6 10 1 6 11 3 6 10 4 8 10 1 11
Sample Output 2:
NO
CPU Timelimit: | 3 seconds |
Memory limit: | 64M |
Grading style: | ioi |