All submissions for this problem are available.
You’re a miner of amber, a precious resource in Transylvania. After a month’s worth of work, you’re going to head back to your hometown. Unfortunately, there appears to be a monster infestation since you’ve been gone, and all the roads have monsters on them. It’s lucky that before you left, your grandmother gifted you an emergency magic spell that can only be used once which will clear all the monsters off the road you’re on.
You have a map of the towns between the mine and your hometown, and you’ve marked them with the number of monsters on each road. Each monster encountered will take away 10 pieces of your hard-owned amber, thus you want to minimize how much amber you lose.
You will be given an input from stdin, each line containing three words/numbers. The first line contains the number of amber you start out with, the starting point and ending point of your journey. All the following lines list a starting city, ending city, and the number of monsters in between. Note that each road is two-way path. There will be a ‘0’ character at the end that signifies the end of input. See example input listed below.
Your program will output to stdout the optimal path as well as where the spell was cast and how many amber you arrive at your hometown with. See example output listed below.
20000 Mines Thotel
Mines Brahmsburg 394
Mines Ninel 4
Brahmsburg Thotel 50
Brahmsburg Ninel 5
Ninel Thotel 600
Mines to Ninel
Ninel to Thotel
Spell was cast between Ninel to Thotel
Arrived to Thotel with 19960 pieces of amber
Note: There is NO newline character at the end of the output.
Also Note: The text "Spell was cast between Ninel to Thotel" comes right before the last line "Arrived to Thotel with 19960 pieces of amber"
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.