15-295 Reading 6 (Wednesday, February 23, 2005)
Assigned Readings
-
First edition: Sections 24.1, 24.2, 25.1, 25.2, 25.4
-
Second edition: Sections 23.1, 23.2, 24.2, 24.3
Problem A: Downhill biking
The nation of Elbonia is a poor third-world country, and most Elbonian
teenagers have no access to modern entertainment, such as amusement parks,
computer games, or even VCRs; they therefore try to
make effective use of freely available outdoor resources. A popular Elbonian
game involves the use of a bike on a large hillside in a rural area. The
purpose is to bike downhill with minimal use of brakes, thus achieving
a dangerously high speed. If the hillside has multiple trails, game participants
may choose a route that matches their skills; beginners take longer downhill
paths, whereas more experienced bikers take the shortest path, thus reaching
a greater speed. Your task it to write a program that finds the shortest
and the longest downhill paths for a given hillside.
Input
The input is a hillside map, which includes downhill trails and their intersections.
The first line contains two positive integers, n and m, separated
by a single space; n is the number of intersections, which is between
2 and 100,000, and m is the number of trails, which is between 1
and 1,000,000. The next m lines represent trails, one trail per
line; the description of a trail includes three integers, separated by
single spaces, where the first integer is the beginning of the trail, the
second is the trail end, and the third is the length of the trail. For
example, the line "2 4 10" describes a downhill trail from intersection
2 to intersection 4, the length of which is 10. The intersection numbers
are between 1 and n, and the trail lengths are between 1 and 100.
We assume that intersection n is below intersection 1 on the hillside,
and that the game participants bike from 1 to n.
Output
If the map includes cycles, the output is the string "Invalid map".
If the map has no cycles, but there is no path from intersection 1 to intersection
n, the output is the string "No route". Finally, if the map
is acyclic, and it includes a path from 1 to n, then the output
consists of two integers, separated by a single space. The first integer
is the length of the shortest path from 1 to n, and the second is
the length of the longest path from 1 to n.
Sample input
4 4
1 2 10
1 3 10
2 3 10
2 4 30
3 4 40
Sample output
40 60
Problem B: Pony tale 2
The Alpine Country of Mountaintops consists of n mountaintops connected
by bridges; each bridge has a weight limit, and safety regulations prohibit
travelers to overload bridges. Every bridge allows travel in both directions,
and the inhabitants of this country never build two different bridges between
the same two mountaintops, which means that their country is a well-defined
undirected graph. The main delivery service in this country is the United
Pony Service (UPS), which allows shipping heavy loads
by ponies; although the ponies were initially afraid of heights, they have
gradually got used to bridges, and they now readily cross all bridges.
When a customer needs to place a delivery order, a UPS
representative asks about the origin and destination mountaintops, and
then computes the maximal weight of a carriage that can travel between
these two mountaintops. Your task is to automate this computation.
Input
The input includes a map of the country and a list of origin-destination
pairs. The first line contains three positive integers, n, m,
and k, separated by single spaces; n is the number of mountaintops,
which is between 2 and 100,000; m is the number of bridges, which
is between 1 and 1,000,000; and k is the number of origin-destination
pairs, which is between 1 and 10. The next m lines describe bridges
between mountaintops, one bridge per line. The description of a bridge
includes three positive integers, separated by single spaces, where the
first two integers are the respective mountaintops, and the third is the
weight limit; for example, the line "2 4 10" describes a bridge between
mountaintops 2 and 4, with weight limit 10. The mountaintop numbers are
between 1 and n, and the weight limits are between 1 and 108.
Finally, the last k lines are origin-destination pairs, one pair
per line; each pair includes two distinct integer numbers, separated by
a single space. For example, the line "1 6" means that a customer has requested
a delivery between mountaintops 1 and 6.
Output
The output includes k lines, which correspond to the given origin-destination
pairs. If the bridges do not allow travel between a given origin and destination,
the respective output line is the string "No route". Else, the output
line is the weight of the heaviest carriage that can travel between the
origin and destination.
Sample input
6 6 2
1 2 10
1 4 60
2 3 20
2 4 10
3 4 30
5 6 10
1 2
1 6
Sample output
20
No route
Problem C: Hiking map
The authorities of a large park have decided to publish an updated map
of the hiking trails in the park; to ensure accuracy, they have hired two
cartographers, asked each cartographer to produce a complete map of the
park, and then compared the resulting maps. Each cartographer has represented
the park as an undirected graph, where edges are trails, and vertices are
their intersections. Unfortunately, they have used different enumeration
of intersections, which complicated the comparison of the maps. Your task
is to write a program that determines whether the two maps are identical,
that is, whether we can convert the first map into the second by re-numbering
intersections.
Input
The input consists of two maps with the same number of trails and intersections.
The first line contains two positive integers, n and m, separated
by a single space; n is the number of intersections, which is between
1 and 50, and m is the number of trails, which is between 1 and
1,000. The next m lines represent trails in the first map, and the
m lines after that represent trails in the second map. The description
of a trail includes two distinct integers between 1 and n, separated
by a single space, which represent the intersections connected by this
trail.
Output
If the two maps are identical, the output is the string "Same map";
else, it is the string "Different maps".
Example input
4 3
1 2
2 3
2 4
1 4
2 4
3 4
Example output
Same map
Hint
This problem does not have a polynomial-time solution, and it may require
heuristic search.