通行料を安くする最適ルートを探し出すプログラム。

Problem J
Toll
---- The 2003 ACM Programming Contest World Finals ----

Sindbad the Sailor sold 66 silver spoons to the Sultan of Samarkand. The selling was quite easy; but delivering was complicated. The items were transported over land, passing through several towns and villages. Each town and village demanded an entry toll. There were no tolls for leaving. The toll for entering a village was simply one item. The toll for entering a town was one piece per 20 items carried. For example, to enter a town carrying 70 items, you had to pay 4 items as toll. The towns and villages were situated strategically between rocks, swamps and rivers, so you could not avoid them.
 「シンドバッドがサマルカンドのサルタンにシルバースプーン66本を売りつけた。売るのは簡単だったけど、配達は大変。アイテムは陸路で運ばれ、いくつかの町と村を通らないといけなかった。すべての町と村では、入る時に通行料が必要だった。ただ、去るときは通行料はいらない。村の通行料は単に1アイテム。町の通行料は20アイテムにつき1つ。例えば、70アイテムをもって町に入ろうとしたら、4アイテムを通行料として支払わないといけない。町、村は岩や沼地、川の間の戦略要所にあり、避けて通ることはできない。」

Figure 1: To reach Samarkand with 66 spoons, traveling through a town followed by two villages, you must start with 76 spoons.
 「図1:町1つ、村2つを通った後に、66本のスプーンをサマルカンドに送り届けるには、76本のスプーンをもって出発しないといけない。」

Figure 2: The best route to reach X with 39 spoons, starting from A, is A→b→c→X, shown with arrows in the figure on the left. The best route to reach X with 10 spoons is A→D→X, shown in the figure on the right. The figures display towns as squares and villages as circles.
 「図2:39本のスプーンをX地点に送り届けるベストルートは、左図の矢印通り、A地点から A→b→c→X というもの。10本のスプーンなら、右図のように、A→D→X がベストルート。図に四角は町、円は村を表す。」

Predicting the tolls charged in each village or town is quite simple, but finding the best route (the cheapest route) is a real challenge. The best route depends upon the number of items carried. For numbers up to 20, villages and towns charge the same. For large numbers of items, it makes sense to avoid towns and travel through more villages, as illustrated in Figure 2.
 「各町や村に徴収される通行料を予測するのは簡単だけど、ベストルート(もっとも安いルート)を探し出すのは難しい。ベストルートが運ぶアイテムの数に依存するから。20本までなら、町も村も通行料が同じ。アイテムの量が多くなると、図2のように、町を避けて、数的に多くても村を選ぶのが賢明だろう。」

You must write a program to solve Sindbad’s problem. Given the number of items to be delivered to a certain town or village and a road map, your program must determine the total number of items required at the beginning of the journey that uses a cheapest route.
 「このシンドバッド問題を解くプログラムを書いて欲しい。目的地に届けるべきアイテムの本数とロードマップが与えられたものとして、プログラムは最も安いルートを利用するときの、出発時に必要なアイテム本数を算出しないといけない。」

Input
The input consists of several test cases. Each test case consists of two parts: the roadmap followed by the delivery details.
 「入力に複数のテストケースが含まれる。各テストケースは2つの部分、つまり、ロードマットと配達任務、からなる。」

The first line of the roadmap contains an integer n, which is the number of roads in the map (0 <= n). Each of the next n lines contains exactly two letters representing the two endpoints of a road. A capital letter represents a town; a lower case letter represents a village. Roads can be traveled in either direction.
 「ロードマップの1行目に整数nが入る。n (0<=n) マップにある道の数を示す。つぎのn行に、道の両端を表す2文字が入る。大文字は町、小文字は村を意味する。道は双方通行可能。」

Following the roadmap is a single line for the delivery details. This line consists of three things: an integer p (0 < p <= 1000) for the number of items that must be delivered, a letter for the starting place, and a letter for the place of delivery. The roadmap is always such that the items can be delivered.
 「ロードマップのつぎにある1行は配達任務を示す。その行は3つのこと、すなわち、整数p (0<p<=1000) 届けるアイテムの本数、出発地となる文字、目的地となる文字、が書かれる。ルートマップは配達可能なものだ。」

The last test case is followed by a line containing the number -1.
 「入力の最後に -1 が入る。」

Output
The output consists of a single line for each test case. Each line displays the case number and the number of items required at the beginning of the journey. Follow the output format in the example given below.
 「出力に、各テストケースに対応する1行をそれぞれ書くこと。各行にテストケースの番号と、出発時に必要なアイテム数を表示すること。サンプル出力データのフォーマットに従うこと。」

Sample Input
1
a Z
19 a Z
5
A D
D X
A b
b c
c X
39 A X
-1

Output for the Sample Input
Case 1: 20
Case 2: 44

Comments are closed.

Post Navigation