시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 52 | 27 | 25 | 56.818% |
We want to create a smartphone application to help visitors of a shopping mall and you have to calculate the shortest path between pairs of locations in the mall. Given the current location of the visitor and his destination, the application will show the shortest walking path (in meters) to arrive to the destination.
The mall has N places in several floors connected by walking paths, lifts, stairs and escalators (automated stairs). Note that the shortest path in meters may involve using an escalator in the opposite direction. We only want to count the distance that the visitor has walked so each type of movement between places has a different cost in meters:
The shortest walking path must use only these connections. All the places are connected to each other by at least one path.
Each input file contains the map of a unique shopping mall and a list of queries.
The first line contains two integers N (N ≤ 200) and M (N −1 ≤ M ≤ 1000), the number of places and connections respectively. The places are numbered from 0 to N-1. The next N lines contain floor and the coordinates x, y of the places, one place per line. The distance between floors is 5 meters. The other two coordinates x and y are expressed in meters.
The next M lines contain the direct connections between places. Each connection is defined by the identifier of both places and the type of movement (one of the following: walking, stairs, lift, or escalator). Check the cost of each type in the description above. The type for places in the same floor is walking.
The next line contains an integer Q (1 ≤ Q ≤ 1000) that represents the number of queries that follow. The next Q lines contain two places each a and b. We want the shortest walking path distance to go from a to b.
For each query write a line with the shortest path in walked meters from the origin to the destination, with each place separated by a space.
6 7 3 2 3 3 5 3 2 2 3 2 6 4 1 1 3 1 4 2 0 1 walking 0 2 lift 1 2 stairs 2 3 walking 3 4 escalator 5 3 escalator 4 5 walking 5 0 1 1 2 3 5 5 3 5 1
0 1 1 0 2 3 4 5 5 3 5 3 2 0 1
ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2013 C번