Task
Umidsh Izadish is a truck driver and wants to drive from a city to another city while there exists a dedicated straight road between each pair of cities in that country. Amount of consumed fuel is the distance between two cities which is computed from their coordinates. There is a gas station in each city, so Umidsh can refuel the gas container of his truck. Your job is to compute the minimum necessary volume of gas container of Umidsh’s Truck.
Input data
The first line of input contains an integer, the number of test cases. Following, there are data for test cases. Each test case begins with a line containing one integer $C$, $2 /leq C /leq 200$, which is the number of cities. The next $C$ lines each contain two integers $x$,$y$ representing the coordinate of one city. First city is the source city and second is the destination city of Umidsh.
Output data
There should be one line for each test case in output. Each line should contain one floating point number which is the minimum necessary volume of truck’s gas container, printed to three decimals.
Tests
| Input | Output |
|
$2$ $2$ $0$ $0$ $3$ $4$ $3$ $17$ $4$ $19$ $4$ $18$ $5$ |
$5.000$ $1.414$ |
|
$1$ $3$ $4$ $5$ $4$ $6$ $4$ $7$ |
$1.000$ |
|
$2$ $4$ $0$ $1$ $0$ $-1$ $1$ $0$ $-1$ $0$ $3$ $8$ $9$ $0$ $1$ $14$ $14$ |
$1.414$ $11.314$ |
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
import java.util.ArrayList; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Scanner; public class TruckDriving { public class Node implements Comparable<Node> { Integer first; Integer second; @Override public int compareTo(Node other) { if (this.first != other.first) { return this.first.compareTo(other.first); } else { return this.second.compareTo(other.second); } } } int distance[] = new int[200]; public TruckDriving() { Scanner sc = new Scanner(System.in); int testCaseCount = sc.nextInt(); for (int i = 0; i < testCaseCount; i++) { int cityCount = sc.nextInt(); ArrayList<Node> coordCity = new ArrayList<Node>(cityCount); for (int j = 0; j < cityCount; j++) { int coordX = sc.nextInt(); int coordY = sc.nextInt(); Node city = new Node(); city.first = coordX; city.second = coordY; coordCity.add(city); } findMinimum(coordCity, cityCount); // System.out.println(distance.get(1)); double res = Math.sqrt(distance[1]); System.out.format("%.3f", res); System.out.println(); } } public void findMinimum(ArrayList<Node> coordCity, int cityCount) { // System.out.println(distance); distance[0] = 0; for (int i = 1; i < cityCount; i++) { distance[i] = Integer.MAX_VALUE; } PriorityQueue<Node> q = new PriorityQueue<Node>(); Node zeroPair = new Node(); zeroPair.first = 0; zeroPair.second = 0; q.add(zeroPair); while (!q.isEmpty()) { int num_v = q.peek().second; Node cur = coordCity.get(num_v); int distv = -q.peek().first; q.poll(); for (int j = 0; j < cityCount; j++) { int distan = Math.max(distv, (cur.first - coordCity.get(j).first) * (cur.first - coordCity.get(j).first) + (cur.second - coordCity.get(j).second) * (cur.second - coordCity.get(j).second)); if (distance[j] > distan) { distance[j] = distan; Node tempPair = new Node(); tempPair.first=-distan; tempPair.second=j; q.add(tempPair); } } } } public static void main(String[] args) { TruckDriving tr = new TruckDriving(); } } |
Solution
We can interpretate the set of the cities as weighted graph, which vertices represent cities and weight of each edge between two vertices is the gas volume required for passing the distance between corresponding cities.
The volume of truck’s gas container depends on the gas volume required for arrival to the each next station of the Umidsh’s way. The maximum between gas volume required to get to the city $A$ and gas volume required to pass the way from the city $a$ to the city $B$ represents the minimum necessary gas volume required to get to the city $B$ through the city $A$. So the volume of truck’s gas container would turn to minimum, when the maximum gas volume required for passing the distance between each two stations of his way would turn to minimum. Thus we could use modified Dijkstra’s algorithm to find the biggest value among the weights of an edges between each two stations of the way between vertice 0 and vertice 1.
Note: To use Node objects in the PriorityQueue, there should be a way to compare this objects. Thus, it was required to overwrite a method CompareTo so that we could implement interface Comparable