poj2253 Frogger dijkstra

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int n, visit[200];
 8 double x[200], y[200];
 9 double G[200][200];
10 double dist[200];
11 const int inf = 2000;
12 
13 void dijkstra() {
14     fill(visit, visit + n, 0);
15     fill(dist, dist + n, inf);
16     dist[0] = 0;
17     for (int i = 0; i < n; i++) {
18         int minn = inf, v;
19         for (int j = 0; j < n; j++) {
20             if (!visit[j] && dist[j] < minn) {
21                 minn = dist[j];
22                 v = j;
23             }
24         }
25         visit[v] = 1;
26         if (v == 1)
27             break;
28         for (int j = 0; j < n; j++) {
29             if (!visit[j])
30                 dist[j] = min(dist[j], max(dist[v], G[v][j]));
31         }
32     }
33 }
34 
35 int main() {
36     int cnt = 0;
37     while (true) {
38         cin >> n;
39         if (n == 0)
40             break;
41         for (int i = 0; i < n; i++)
42             cin >> x[i] >> y[i];
43         for (int i = 0; i < n; i++) {
44             for (int j = 0; j < n; j++)
45                 G[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
46         }
47         dijkstra();
48         printf("Scenario #%d\n", ++cnt);
49         printf("Frog Distance = %.3lf\n\n", dist[1]);
50     }
51     return 0;
52 }