ローワンさんはパリのウォーキングツアーを計画しています。しかし、彼は少し怠け者なので、行きたい場所をすべて通る最短経路をたどりたいと思っています。彼はバスで最初の場所に行き、最後の場所から別の場所に戻る予定なので、開始場所と終了場所を自由に選択できます。あなたは彼を助けることができますか？
入力
入力の最初の行には、訪問する場所の数 (n) が含まれています。次に、次の n 行で、訪問する各場所の座標を見つけます。次に例を示します。
3
132 73
49 86
72 111
出力
テスト ケースごとに、ある場所から別の場所への徒歩距離がユークリッド距離であると仮定して、Rowan 氏がすべての場所を訪れるために歩かなければならない最小距離を含む 1 行をプログラムで出力する必要があります。アルゴリズムは、小数点の右側に正確に 3 桁の数字を固定小数点表記で出力し、先頭にスペースを入れない必要があります。訪問する場所は最大で 12 か所あります。例
入力例:
3
132 73
49 86
72 111
出力例:
104.992
私は宿題のためにこのコードに取り組んできましたが、うまくいかず、これが最善のアプローチであるかどうか疑問に思い始めました..
問題は floyd-warshall 関数です。floydwarshall(path, n, next); の前後で 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;
}