POJ 2253 Frogger（dijkstra变形）

题意：

有两只青蛙A和B，现在青蛙A要跳到青蛙B的石头上，中间有许多石头可以让青蛙A弹跳。给出所有石头的坐标点，求出在所有通路中青蛙需要跳跃距离的最小值。

思路：

dijkstra算法的变形。本来是dist是记录最短距离，在这道题中可以把它变为已经跳过的最大距离，稍微改一下松弛算法就可以。具体见代码。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 const int maxn = 200 + 5;
 9 const int INF = 0x3f3f3f3f;
10 
11 int n;
12 int x[maxn], y[maxn];
13 double dist[maxn];
14 int vis[maxn];
15 
16 double cacl(int x1, int y1, int x2, int y2)
17 {
18     return sqrt((double)(x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
19 }
20 
21 void dijkstra()
22 {
23     memset(vis, 0, sizeof(vis));
24     for (int i = 0; i < n; i++)
25     {
26         bool flag = false;
27         double MIN = INF;
28         int u;
29         for (int j = 1; j < n; j++)
30         {
31             if (!vis[j] && dist[j] < MIN)
32             {
33                 MIN = dist[j];
34                 flag = true;
35                 u = j;
36             }
37         }
38         if (!flag)   break;
39         if (u == 1)  break;
40         vis[u] = 1;
41         for (int j = 1; j < n; j++)
42         {
43             if (!vis[j] && dist[j]> max(dist[u], cacl(x[u], y[u], x[j], y[j])))
44                 dist[j] = max(dist[u],cacl(x[u], y[u], x[j], y[j]));
45         }
46     }
47 }
48 
49 int main()
50 {
51     //freopen("D:\txt.txt", "r", stdin);
52     int kase = 0;
53     while (~scanf("%d",&n) && n)
54     {
55         for (int i = 0; i < n; i++)
56             scanf("%d%d", &x[i], &y[i]);
57         for (int i = 1; i < n; i++)
58         {
59             dist[i] = cacl(x[0], y[0], x[i], y[i]);
60         }    
61         dijkstra();
62         printf("Scenario #%d
", ++kase);
63         printf("Frog Distance = %.3f

", dist[1]);
64     }
65     return 0;
66 }