1 Star 0 Fork 1

saigon/Algorithms

forked from charlieshu/Algorithms 
Create your Gitee Account
Explore and code with more than 12 million developers,Free private repositories !:)
Sign up
文件
Clone or Download
P1433奶酪.cpp 1.60 KB
Copy Edit Raw Blame History
charlie authored 2024-01-09 00:01 . move from github to gitee
#include <iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
using namespace std;
static int n = 0;
double dist(double x1, double y1, double x2, double y2){
return sqrt(pow(x1-x2, 2.0)+pow(y1-y2,2.0));
}
double minDist(double * points, int startPoint, int * usedPath, int usedSize,int n){
double md = 100000, temp;
int newUsedPath[n];
//printf("startPoint=%d, usedSize=%d , n=%d", startPoint, usedSize, n);
for(int i=0;i<n;i++){
// cout<<"check usedPath["<<i<<"]="<<usedPath[i]<<endl;
if(usedPath[i]){
if(usedSize == n-1){
// cout<<"return";
return dist(points[startPoint*2], points[startPoint*2+1], points[i*2], points[i*2+1]);
}else{
memcpy(newUsedPath, usedPath, n);
newUsedPath[i] = 0;
temp = minDist(points, i, newUsedPath, usedSize+1,n)+dist(points[startPoint*2], points[startPoint*2+1], points[i*2], points[i*2+1]);
newUsedPath[i] = 1;
}
if(temp<md){
// cout<<"change md from "<<md<<" to "<<temp<<" when startPoint="<<startPoint<<" endPoint="<<i<<endl;
md = temp;
}
// cout<<"from "<<i<<" to left "<<usedSize-1<<" dist "<<md<<endl;
}
}
return md;
}
int main(){
//1. input
cin>>n;
n++;
double points[n][2];
points[0][0] = 0;
points[0][1] = 0;
int usedPath[n];
for(int i=1;i<n;i++){
cin>>points[i][0]>>points[i][1];
usedPath[i] = 1;
}
//memset(usedPath,1,sizeof(usedPath));
//2. calc
usedPath[0] = 0;
double md = minDist(&points[0][0], 0, &usedPath[0], 1,n);
printf("%.2f",md);
}
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
C++
1
https://gitee.com/saigonshu/algorithm.git
git@gitee.com:saigonshu/algorithm.git
saigonshu
algorithm
Algorithms
master

Search

0d507c66 1850385 C8b1a773 1850385