罗文先生计划徒步游览巴黎。不过，由于他有点懒惰，所以他想走最短的路径，穿过他想去的所有地方。他计划从第一个地方坐公共汽车，从最后一个地方再坐一辆，所以他可以自由选择起点和终点。你能帮助他吗？
输入
输入的第一行包含访问地点的数量 (n)。然后，在接下来的 n 行中，您找到每个要访问的地方的坐标。这是一个例子：
3
132 73
49 86
72 111
输出
对于每个测试用例，假设从一个地方到另一个地方的步行距离是欧几里得距离，您的程序应该输出一行，其中包含 Rowan 先生访问所有地方必须步行的最短距离。该算法应该以定点表示法输出一个数字，小数点右侧恰好有 3 位数字，并且没有前导空格。最多有12个地方可以参观。例子
示例输入：
3
132 73
49 86
72 111
示例输出：
104.992
我一直在为我的家庭作业编写这段代码，但我无法让它工作，我开始想知道这是否是最好的方法..
问题是 floyd-warshall 函数，它对 float **path 结构没有任何作用.. 不知道为什么.. 在 floydwarshall(path, n, next) 之前和之后路径是相同的；
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <float.h>
/*Implementing of http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm*/
struct point {
float x;
float y;
};
float cost(struct point* a, struct point* b) {
return sqrt(pow((*a).x - (*b).x, 2) + pow((*a).y - (*b).y, 2));
}
float** f2dmalloc(int n, int m){
int i;
float **ptr;
ptr = malloc(n * sizeof(float *));
for (i = 0; i < n; i++) {
ptr[i] = calloc(m, sizeof(float));
}
return ptr;
}
void floydwarshall(float **path, int n, float ** next){
int i, j, k;
float a, b;
for (k = 0; k < n; k++) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
a = path[i][j];
b = path[i][k] + path[k][j];
path[i][j] = ((a) < (b) ? a : b);
next[i][j] = k;
}
}
}
}
int main (int argc, const char* argv[])
{
int i;
int j;
int n;
float temp;
float mininum;
scanf("%d", &n);
/*
A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
from i to j using intermediate vertices (1..k−1). Each path[i][j] is initialized to
cost(i,j).
*/
float ** path;
float ** next;
struct point* points;
path = f2dmalloc(n, n);
next = f2dmalloc(n, n);
points = malloc(n * sizeof(struct point));
for (i = 0; i < n; i++){
scanf("%f %f", &(points[i].x), &(points[i].y));
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
path[i][j] = cost(&points[i], &points[j]);
}
}
temp = 0;
for (i = 0; i < n; i++) {
mininum = FLT_MAX;
for (j = 0; j < n; j++) {
printf("%.3f\t", path[i][j]);
if (path[i][j] < mininum && path[i][j] != 0){
mininum = path[i][j];
}
}
printf("\tminimum - %.3f\n", mininum);
temp += mininum;
}
floydwarshall(path, n, next);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%.3f\t", next[i][j]);
}
printf("\n");
}
/*
temp = 0;
for (i = 0; i < n; i++) {
mininum = FLT_MAX;
for (j = 0; j < n; j++) {
printf("%.3f\t", path[i][j]);
if (path[i][j] < mininum && path[i][j] != 0){
mininum = path[i][j];
}
}
printf("\tminimum - %.3f\n", mininum);
temp += mininum;
}
printf("%.3f\n", temp);
*/
return 0;
}