題目連結: https://onlinejudge.org/external/2/216.pdf
題目大意: 問每個點到點總路徑最短多長。並記錄那個路徑
思路: TSP問題,n = 8,可以直接枚舉 N! 解。用 STL next_permutation. 直接排列組合 代碼簡潔。用一個陣列紀錄最佳排列組合。
代碼:
#include <bits/stdc++.h>
using namespace std;
int o[10], x[10], y[10], ans[10];
int main()
{
//freopen("out.txt", "w", stdout);
int n, cas = 1;
while(cin >> n, n){
for(int i = 0; i < n; ++i)
cin >> x[i] >> y[i], o[i] = i;
double mn = 1e9;
do{
double sum = 0;
for(int i = 1; i < n; ++i){
sum += (sqrt(pow(x[o[i]]-x[o[i-1]],2.0)+pow(y[o[i]]-y[o[i-1]],2.0))+16.0);
}
if(sum < mn) memcpy(ans, o, sizeof o), mn = sum;
}while(next_permutation(o, o+n));
puts("**********************************************************");
printf("Network #%d\n", cas++);
for(int i = 1; i < n; ++i){
double dis = sqrt(pow(x[ans[i]]-x[ans[i-1]],2.0)+pow(y[ans[i]]-y[ans[i-1]],2.0))+16.0;
printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.\n", x[ans[i-1]], y[ans[i-1]],
x[ans[i]], y[ans[i]], dis);
}
printf("Number of feet of cable required is %.2f.\n", mn);
}
return 0;
}
留言列表