CourierProblem code: DCE02 |
The ship Titanic is very huge. It is often required by the staff to take things from 1 place to other.
Given the cost of possible paths through different levels, return the minimum cost of the path taken from the top level to the bottom level. ( It is not necessary that all the sectors are connected. There will always be a path from topmost level to lowest level. )
Input
The first line contains two space separated integers n, k. Where n is the number of sectors on the topmost level, and k is the number of levels in the ship.
From the next line onwards, three space separated integers are given. First integer is the starting sector from 1st level, 2nd integer is the destination in the 2nd level, and 3rd integer is the cost of path. (The sources and destinitions are 1-based)
The integer -1 signifies the end of paths for the given pair of levels.
The next lines contain the paths for next pair of levels till a -1is encountered, and so on.
(So the total number of -1 encountered are k-1)
Output
A single line containing the minimum cost to travel from topmost level to lowest level.
Example
Input: 5 2 1 1 1 2 2 2 1 3 3 3 1 6 5 4 9 -1 Output: 1 Explanation: There are just two levels. The shortest path is from sector 1 on level 1 to sector 1 on level 2.
| Author: | uploader0 |
| Date Added: | 14-10-2009 |
| Time Limit: | 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Please ignore submissions
Please ignore submissions made by Sailesh Mittal.
What are the constraints of
What are the constraints of different parameters ? Is it possible to move between sectors on same levels (seemingly not, just confirming)? And why is n given ? Isn't n visible while encountering the first -1 itself ? And total cost fits within a 4 byte int , right ?
Thanks
Constraints: n<=1000, k<n. It
Constraints: n<=1000, k<n.
It is not possible to move between sectors on same level.
n is not visible while encountering the first -1. There may not be a path from one sector to another in a pair of levels. It may be visible by the number of -1s encountered though.
It is not possible to move
It is not possible to move between sectors on the same level.
n gives the number of sectors on the first level(deck). -1 is encountered when all the edges from a level to the next level are over. The number of edges and number of sectors in a level might not be same.
Other things you have to figure out yourself!
Best of luck!
Sorry but it is still
Sorry but it is still unclear. The number of -1 is always k-1. So, there will be k-1 sets of edges giving edges b/w 1st and 2nd,2nd and 3rd,....second last to last levels. So, the 1st set automatically tells us which of the relevant sectors in topmost level are there. This is assuming that all triplets of sector1,sector2,cost are valid.
Can you please give an example test case where n is needed ?
@Sailesh
You said that "There may not be a path from one sector to another in a pair of levels. It may be visible by the number of -1s encountered though.". No. of -1 is always k-1 .. so what does this statement mean ?
I guess there is something I am missing totally.
Sorry for the earlier post.
Sorry for the earlier post. The no. of -1s only tells the value of k. The n is for the structure of ship. You may ignore it if you dont require it in the solution.
Structure of the ship: A ship
Structure of the ship:
A ship is represented in sectors as below:
n is the number of sectors in the topmost level, k is the number of levels.
The first(topmost) level contains n sectors, 2nd contains n-1 sectors, and the k-th(lowermost) sector contains n-k+1 sectors.
can you please check the
can you please check the correctness of test cases i/o.