
Number Triples
|
All submissions for this problem are available.
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, \quad A_1 W_1 A_2, \quad A_2 W_2 A_3, \quad ... A_{k-2} W_{k-2} A_{k-1}, \quad A_{k-1} W_{k-1} A_k$$ such that - $A_0 = A$ - $A_k = B$ For each $i$, $0 \leq 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, \quad 6 \; 3 \; 11$$ The value of this chain is $1+3 = 4$. Here is another chain connecting $1$ and $11$. $$1 \; 1 \; 6, \quad 6 \; 1 \; 10, \quad 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: - The first line of the input has three numbers $M$, $A$ and $B$, where $M$ is the number of triples, and your task is to find the value of the least value chain connecting $A$ and $B$. - The next $M$ lines (lines $2,3, \ldots,M+1$) describe the triples. Line $i+1$ contains the three positive integers $X_i$, $Y_i$ and $Z_i$ that make up the $i^{th}$ triple. ###Output: - 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. ###Constraints: - $1 \leq M \leq 4000000$ - $1 \leq A, B \leq 2000$ - $1 \leq X_i, Y_i, Z_i \leq 2000$ ###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: NOAuthor: | admin2 |
Date Added: | 17-09-2018 |
Time Limit: | 2 sec |
Source Limit: | 50000 Bytes |
Languages: | C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS |
Comments
- Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
