POJ Frogger--Dijkstra算法
?
Description
一只叫Freddy的青蛙蹲坐在湖中的一块石头上。突然他发现一只叫Fiona的青蛙在湖中的另一块石头上。Freddy想要跟Fiona约会，但由于湖水太脏，他不想游泳过去而是跳过去找Fiona。
很不幸，Fiona所在的石头距离他有点远，甚至超出了他的跳跃能力。然而Freddy注意到湖中还有一些其他的石头。这些石头也许会将这个很长的跳跃距离化成若干个短的跳跃距离。
我们定义“青蛙距离”为Freddy跳到Fiona那里所需要的若干次跳跃中最长的那一次。现在给你Freddy，Fiona，以及湖中其他石头的坐标，让你求出最短的“青蛙距离”。
Input
输入有可能是多组测试数据。每组数据的第一行有一个整数n(2<=n<=200)，表示湖中一共有多少块石头。接下来的n行，每一行有两个整数xi，yi(0 <= xi,yi <= 1000)，表示第i块石头的坐标。第1块石头的坐标是Freddy所在的位置，第二块石头的坐标是Fiona所在的位置，其他的石头上都没有青蛙。当输入n=0的时候，程序结束。
Output
对于每一组测试数据，先输出一行"Scenario #x"，然后在下一行输出"Frog Distance = y"。其中x表示当前是第几组测试数据，y为该组数据的最小“青蛙距离”。每两组测试数据之间输出一个空行。
Sample Input20 03 4317 419 418 50
Sample OutputScenario #1Frog Distance = 5.000Scenario #2Frog Distance = 1.414
这个题目的意思太难理解了，我开始还以为是从第一个点到第二个点之间的最短距离，可结果错了。原来是求从第
一个节点到第二个节点的生成的最小二叉树中的最大长度。好了不罗嗦了，直接看代码吧！
#include <stdio.h>#include <string.h>#include <math.h>#define INFINITE 999999999.9#define N 201double getLength(double x1, double y1, double x2, double y2){ /*求两点之间的距离*/ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}double Dijkstra(double map[N][N], int v, int n, int m){ int i; int s[N]; //s[i]=0代表顶点未入S集,s[i]=1表示顶点i已入S集 double dist[N]; //dist[i]表示当前已知的从源点到顶点i的最短路径的长度 double min, max; int u; for(i = 0; i < n; i++) { dist[i] = map[v][i]; s[i] = 0; } s[v] = 1; //初始时v进入s集 dist[v] = 0; max = 0; u = v; while(u != m) { min = INFINITE; for(i = 0; i < n; i++) //求源点u到其他顶点i的最短距离 { if(!s[i] && (dist[i] < min)) { u = i; min = dist[i]; } } if(min > max) max = min; s[u] = 1; //将u加入s集 for(i = 0; i < n; i++) { if(!s[i] && (map[u][i] < INFINITE) && (map[u][i] < dist[i])) { dist[i] = map[u][i]; } } } return max;}int main(){ int i, j, k; int n, count = 0; double map[N][N]; int x[N], y[N]; while(scanf("%d", &n) && n) { for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { map[i][j] = INFINITE; } scanf("%d %d", &x[i], &y[i]); } for(i = 0; i < n; i++) { /*建图*/ for(j = 0; j < n; j++) { map[i][j] = getLength(x[i], y[i], x[j], y[j]); } } printf("Scenario #%d\n", ++count); printf("Frog Distance = %.3lf\n\n", Dijkstra(map, 0, n, 1)); } return 0;}?
Scenario #1Frog Distance = 5.000Scenario #2Frog Distance = 1.414
这个题目的意思太难理解了，我开始还以为是从第一个点到第二个点之间的最短距离，可结果错了。原来是求从第一个节点到第二个节点的生成的最小二叉树中的最大长度。好了不罗嗦了，直接看代码吧！
#include <stdio.h>#include <string.h>#include <math.h>#define INFINITE 999999999.9#define N 201double getLength(double x1, double y1, double x2, double y2){ /*求两点之间的距离*/ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}double Dijkstra(double map[N][N], int v, int n, int m){ int i; int s[N]; //s[i]=0代表顶点未入S集,s[i]=1表示顶点i已入S集 double dist[N]; //dist[i]表示当前已知的从源点到顶点i的最短路径的长度 double min, max; int u; for(i = 0; i < n; i++) { dist[i] = map[v][i]; s[i] = 0; } s[v] = 1; //初始时v进入s集 dist[v] = 0; max = 0; u = v; while(u != m) { min = INFINITE; for(i = 0; i < n; i++) //求源点u到其他顶点i的最短距离 { if(!s[i] && (dist[i] < min)) { u = i; min = dist[i]; } } if(min > max) max = min; s[u] = 1; //将u加入s集 for(i = 0; i < n; i++) { if(!s[i] && (map[u][i] < INFINITE) && (map[u][i] < dist[i])) { dist[i] = map[u][i]; } } } return max;}int main(){ int i, j, k; int n, count = 0; double map[N][N]; int x[N], y[N]; while(scanf("%d", &n) && n) { for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { map[i][j] = INFINITE; } scanf("%d %d", &x[i], &y[i]); } for(i = 0; i < n; i++) { /*建图*/ for(j = 0; j < n; j++) { map[i][j] = getLength(x[i], y[i], x[j], y[j]); } } printf("Scenario #%d\n", ++count); printf("Frog Distance = %.3lf\n\n", Dijkstra(map, 0, n, 1)); } return 0;}??