題意描述:
公青蛙a要找到母青蛙b,他要跳過若干塊石頭到達b處,他并不關心走過總路程的長短,但是希望單次跳動的長度最短。
最短路Dijkstra算法。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN 210
#define MAX 100000
typedef struct 

{
double x;
double y;
}Point;
int main()

{
int i, j;
int n;
int x, y;
double mp[LEN][LEN];
Point ps[LEN];
scanf("%d", &n);
int count = 1;
while(n != 0)
{
//
//printf("n = %d\n", n);
//
for(i = 0; i < n; i++)
scanf("%lf%lf", &ps[i].x, &ps[i].y);
for(i = 0; i < n; i++)
for(j = i + 1; j < n; j++)
{
double dx = ps[i].x - ps[j].x;
double dy = ps[i].y - ps[j].y;
mp[i][j] = mp[j][i] = sqrt(dx * dx + dy * dy);
}
for(i = 0; i < n; i++)
mp[i][i] = MAX;
double minlenall = -MAX;
int s[LEN] =
{0};
double cost[LEN];
int pre[LEN];
for(i = 0; i < n; i++)
{
cost[i] = mp[0][i];
if(mp[0][i] != MAX)
pre[i] = 0;
else
pre[i] = -1;
}
s[0] = 1;
pre[0] = -1;
for(j = 0; j <= n - 2; j++)//dijkstra
{
int t = 0;
double min = MAX;
for(i = 0; i < n; i++)//find min
if(s[i] == 0 && cost[i] < min)
{
min = cost[i];
t = i;
}
s[t] = 1;// into S[]
for(i = 0; i < n; i++)//update
{
if(s[i] == 0 && mp[t][i] < cost[i])
{
cost[i] = mp[t][i];
pre[i] = t;
}
}
}
int tt = 1;
int tt1 = pre[tt];
while(pre[tt] != -1)
{
if(mp[tt][tt1] > minlenall)
minlenall = mp[tt][tt1];
tt = tt1;
tt1 = pre[tt1];
}
printf("Scenario #%d\n", count++);
printf("Frog Distance = %.3lf\n\n", minlenall);
scanf("%d", &n);
}
//system("pause");
}

