一、题目

　Frogger

二、分析

　题意关键点就是那个青蛙距离。就是所有1到2的点的路径中，每条路径都可以确定一个最大值，这个最大值就是青蛙要跳的青蛙距离，然后要求这个青蛙距离最小值。

　其实就是最短路的变形，用dijkstra，原先求最短路的时候是每次确定当前最小距离的点，那么，这题只需要每次确定一个当前最有值就可以了，易证，队列后面的值是不会有更小了的。

三、AC代码

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8 #define INF 0x3f3f3f3f
9 typedef pair P;
10 const int MAXN = 2e2 + 14;
11 struct point
12 {
13 int x, y;
14 }node[MAXN];
15 struct cmp
16 {
17 bool operator()(const P &a, const P &b)
18 {
19 return a.first > b.first;
20 }
21 };
22 int n;
23 double G[MAXN][MAXN];
24 double dist[MAXN];
25 bool flag[MAXN];
26
27 void Dijkstra(int s)
28 {
29 priority_queue, cmp> pq;
30 memset(dist, 0, sizeof(dist));
31 memset(flag, 0, sizeof(flag));
32 pq.push(P(0, 1));
33 while( !pq.empty() )
34 {
35 P t = pq.top();
36 pq.pop();
37 int v = t.second;
38 if(flag[v])
39 continue;
40 flag[v] = 1;
41 dist[v] = t.first;
42 for(int i = 1; i <= n; i++)
43 {
44 if(!flag[i])
45 {
46 double m = max(dist[v], G[v][i]);
47 pq.push(P(m, i));
48 }
49 }
50 }
51
52 }
53
54
55 double calc(point a, point b)
56 {
57 double ans;
58 double x = a.x - b.x;
59 double y = a.y - b.y;
60 ans = sqrt(x*x + y*y);
61 return ans;
62 }
63
64
65 int main()
66 {
67 //freopen("in.txt", "r", stdin);
68 int Case = 1;
69 while(scanf("%d", &n) != EOF)
70 {
71 if(n == 0)
72 break;
73 if(Case != 1)
74 puts("");
75 for(int i = 1; i <= n; i++)
76 {
77 scanf("%d%d", &node[i].x, &node[i].y);
78 }
79 for(int i = 1; i <= n; i++)
80 {
81 for(int j = i+1; j <= n; j++)
82 {
83 G[i][j] = calc(node[i], node[j]);
84 G[j][i] = G[i][j];
85 }
86 G[i][i] = 0;
87 }
88 Dijkstra(1);
89 printf("Scenario #%d\n", Case++);
90 printf("Frog Distance = %.3f\n", dist[2]);
91 };
92 return 0;
93 }