Benutzer-Werkzeuge
public:wettbewerbe:getconnected:aufgaben:toll
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen gezeigt.
|
public:wettbewerbe:getconnected:aufgaben:toll [2010-02-08 20:13] ignaz angelegt |
public:wettbewerbe:getconnected:aufgaben:toll [2010-02-09 10:35] (aktuell) ignaz |
||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| ====== Toll ====== | ====== Toll ====== | ||
| + | ===== Description ===== | ||
| + | |||
| + | You are a truck driver that needs to deliver some cargo from one city to another. To accomplish this you are going to use the road network. A road connects exactly 2 cities. Not all cities are directly connected. For example if you want to get from the city A to the city B but the only roads that exist connect A with C and B with C then you will have to pass through the city C. Between 2 cities there is at most one road. Roads may always be used in both direction. Don't make any further assumptions about the topology of the road network. To pass a road you have to pay a tax of x€. All roads cost the same regardless of their length. | ||
| + | |||
| + | How much do you have to pay at least to complete your trip? | ||
| + | |||
| + | ===== Input ===== | ||
| + | |||
| + | The input begins with a single positive integer T on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. | ||
| + | |||
| + | Each test case starts with a line containing 5 positive integers: x, n, m, s and t. | ||
| + | * x is tax amount you have to pay per road (1≤x≤1000) | ||
| + | * n is the number of cities. The cities are number from 1 to n. (1≤n≤10000) | ||
| + | * m is the number of roads. (1≤m≤10000) | ||
| + | * s is the city you start in. (1≤s≤n) | ||
| + | * t is the city you want to get to. (1≤t≤n) | ||
| + | |||
| + | After that the test case contains m lines each describing a road using its 2 end cities. | ||
| + | |||
| + | ===== Output ===== | ||
| + | |||
| + | The output should contain exactly T lines. The t-th line should contain the the amount you have to pay for the t-th testcase or -1 if you can't reach the city t. A line ends per definition with a newline character. | ||
| + | |||
| + | ===== Sample Input ===== | ||
| + | |||
| + | <code> | ||
| + | 3 | ||
| + | |||
| + | 3 3 2 1 2 | ||
| + | 1 3 | ||
| + | 3 2 | ||
| + | |||
| + | 100 5 6 4 3 | ||
| + | 1 3 | ||
| + | 2 4 | ||
| + | 5 1 | ||
| + | 3 2 | ||
| + | 4 1 | ||
| + | 2 5 | ||
| + | |||
| + | 42 6 6 1 6 | ||
| + | 1 2 | ||
| + | 2 3 | ||
| + | 3 1 | ||
| + | 4 5 | ||
| + | 5 6 | ||
| + | 6 4 | ||
| + | </code> | ||
| + | |||
| + | ===== Sample Output ===== | ||
| + | |||
| + | <code> | ||
| + | 6 | ||
| + | 200 | ||
| + | -1 | ||
| + | </code> | ||
public/wettbewerbe/getconnected/aufgaben/toll.1265656385.txt.gz · Zuletzt geändert: 2010-02-08 20:13 von ignaz
Seiten-Werkzeuge
