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 ≤ C ≤ 200)$, which is the number of cities. The next $C$ lines each contain two integers $x$, $y$ $(0 ≤ x, y≤ 1000)$ 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$ |
| $3$ $2$ $1$ $1$ $1$ $2$ $5$ $8$ $6$ $3$ $3$ $4$ $1$ $7$ $7$ $5$ $0$ $3$ $1$ $1$ $1$ $3$ $2$ $5$ |
$1.000$ $5.657$ $2.000$ |
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 |
#include <iostream> #include <iomanip> #include <cmath> #include <algorithm> #include <vector> #include <queue> using namespace std; const int inf = 10000000; struct node { int x; int y; }; vector <node> cities; int d [200]; void diikstra ( int n ){ d[0] = 0; for (int i = 1; i < n; i++){ d[i] = inf; } priority_queue < pair <int, int> > q; q.push({d[0], 0}); while (!q.empty()) { int num_v = q.top().second; node cur = cities[num_v]; int distv = -q.top().first; q.pop(); for (int i = 0; i < n; i++) { int distance = max (distv, (cur.x - cities[i].x)*(cur.x - cities[i].x)+(cur.y - cities[i].y)*(cur.y - cities[i].y)); if(d[i] > distance){ d[i] = distance; q.push ({-distance, i}); } } } } int main() { cout.precision(3); int q; cin >> q; for (int w = 0; w < q; w++){ int n; cin >> n; for (int i = 0; i < n; i++){ int a, b; cin >> a >> b; cities.push_back({a,b}); } diikstra (n); for (int i = 0; i < n; i++){ cities.pop_back(); } cout << fixed << sqrt(d[1]) << endl; } return 0; } |
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.
References
The task at E-Olymp
My solution at ideone