POJ 2253 Frogger（dijkstra变形）

题意：

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

思路：

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

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<cstring>

 #include<cmath>

 using namespace std;

 const int maxn =  + ;

 const int INF = 0x3f3f3f3f;

 int n;

 int x[maxn], y[maxn];

 double dist[maxn];

 int vis[maxn];

 double cacl(int x1, int y1, int x2, int y2)

 {

     return sqrt((double)(x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));

 }

 void dijkstra()

 {

     memset(vis, , sizeof(vis));

     for (int i = ; i < n; i++)

     {

         bool flag = false;

         double MIN = INF;

         int u;

         for (int j = ; j < n; j++)

         {

             if (!vis[j] && dist[j] < MIN)

             {

                 MIN = dist[j];

                 flag = true;

                 u = j;

             }

         }

         if (!flag)   break;

         if (u == )  break;

         vis[u] = ;

         for (int j = ; j < n; j++)

         {

             if (!vis[j] && dist[j]> max(dist[u], cacl(x[u], y[u], x[j], y[j])))

                 dist[j] = max(dist[u],cacl(x[u], y[u], x[j], y[j]));

         }

     }

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     int kase = ;

     while (~scanf("%d",&n) && n)

     {

         for (int i = ; i < n; i++)

             scanf("%d%d", &x[i], &y[i]);

         for (int i = ; i < n; i++)

         {

             dist[i] = cacl(x[], y[], x[i], y[i]);

         }

         dijkstra();

         printf("Scenario #%d\n", ++kase);

         printf("Frog Distance = %.3f\n\n", dist[]);

     }

     return ;

 }