Мр.Роуэн планирует совершить пешеходную экскурсию по Парижу.Однако, поскольку он немного ленив, он хочет выбрать кратчайший путь, который проходит через все места, которые он хочет посетить.Он планирует сесть на автобус до первого места, а другой - до последнего, чтобы он мог свободно выбирать начальное и конечное места.Можете ли вы помочь ему?
Ввод
Первая строка ввода содержит количество мест для посещения (n).Затем в следующих n строках вы найдете координаты каждого места для посещения.Вот пример:
3
132 73
49 86
72 111
Выходные данные
Для каждого тестового примера ваша программа должна вывести одну строку, содержащую минимальное расстояние, которое г-н Роуэн должен пройти, чтобы посетить все места, при условии, что расстояние ходьбы от одного места до другого является евклидовым расстоянием,Алгоритм должен выводить число в записи с фиксированной запятой точно с 3 цифрами справа от десятичной запятой и без начального пробела.Есть не более 12 мест для посещения.Пример
Пример ввода:
3
132 73
49 86
72 111
Пример вывода:
104.992
Я работал над этим кодом, длямоя домашняя работа, но я не могу заставить ее работать, я начинаю задаваться вопросом, является ли это лучшим подходом ..
проблема в функции floyd-warshall, которая ничего не делает с плавающей ** структурой пути .. не знаю почему.. путь одинаков до и после floydwarshall (путь, n, следующий);
#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;
}