|Online Judge||Problem Set||Authors||Online Contests||User|
Which Way Do I Go?
You've decided that the time is right for the next Internet map startup. Your inspiration for this venture is your directionally impaired spouse, who doesn't care for the shortest or quickest routes generated by current online map systems-instead, easier is better.
The backbone of your operation is, of course, your algorithm for calculating directions. Your algorithm must accept the map from your massive database of the entire country and produce the best route that meets the customer's query. Queries consist of an origin, destination, and the optimization goal, which can be for the shortest route, fastest route, or route with the fewest turns. You are guaranteed that there will be a path between source and destination for any query asked.
There are three sections in the input file, the first lists the cities, the second lists the roads, and the third lists the queries.
The first line of input is the number of cities, c, followed by c lines each containing the name of a city. There is no whitespace in a city name.
The next line is the number of roads, r, followed by r lines describing a road. Each road description has the following form:
< RoadName > < CityA > < ABDistance > < ABTime > < CityB > [< BCDist > < BCTime > < CityC > [...]]
There is no whitespace in a road's name. Roads may pass through any number of cities. The cities appear in the order the road passes through them. No road passes through the same city multiple times. Roads are bidirectional. The distance and time (both real numbers) it takes to follow a road between each pair of cities is the distance and time listed between those two names.When following a road between multiple cities (A to C, for example), the distance and time is cumulative for all steps along the path.
The remainder of the lines in the file each list one query. Queries are of the form:
< querytype > < origin > < destination >
Querytype is one of time, distance, or turns and the origin and destination are the names of cities.
The queries end at end-of-file.
For each query, your output will begin with a line:
from < origin >
Each following line will be of the form:
< roadName > to < cityname >
which lists the road to turn onto from the previous city, and the city to take that road to. If a single road is followed between multiple cities, only the final city reached on that road before turning onto another road is listed. The final city listed will be the destination city.
5 Chicago DesMoines OklahomaCity Dallas LosAngeles 4 I80 Chicago 300 4 DesMoines I35 DesMoines 550 7.3 OklahomaCity 205 3 Dallas I40 OklahomaCity 1330 20.5 LosAngeles Rt66 Chicago 2448 46 LosAngeles time Chicago LosAngeles turns Chicago LosAngeles
from Chicago I80 to DesMoines I35 to OklahomaCity I40 to LosAngeles from Chicago Rt66 to LosAngeles
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator