1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| #include<bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
vector<pair<int,int> >v;
double graph[20][20], TSP;
int n;
vector<int> path;
void path_print(){
//cerr<<"Enter---\n";
//for(int i = 0; i < path.size(); i++)cout << path[i] << " ";
//cout << endl;
for(int i = 0; i < path.size()-1; i++){
int x = path[i];
int y = path[i+1];
cout <<"Cable requirement to connect ("<<v[x].first<<","<<v[x].second<<") to ("<<v[y].first<<","<<v[y].second<<") is "<<fixed<<setprecision(2)<<graph[x][y]<<" feet.\n";
cerr << v[x].first << " "<<v[x].second<<endl;
}
}
double tsp(int s, double mn)
{
vector<int>vertex;
for(int i = 0; i < n; i++){
if(i != s)
vertex.push_back(i);
}
double min_path = 99999999.0;
do{
double current_pathweight = 0.0;
int k = s;
for(int i = 0; i < vertex.size(); i++){
current_pathweight += graph[k][vertex[i]];
k = vertex[i];
}
//current_pathweight += graph[k][s];
//min_path = min(min_path, current_pathweight);
if(min_path > current_pathweight && mn > current_pathweight){
min_path = current_pathweight;
path.clear();
path.push_back(s);
for(int i = 0; i < vertex.size(); i++)path.push_back(vertex[i]);
}
}while(next_permutation(vertex.begin(), vertex.end()));
return min_path;
}
void print()
{
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cout << setw(3)<<graph[i][j] << " ";
}
cout << endl;
}
}
int main()
{
//FASTIO
/*
//double start_time = clock();
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
//*/
int cnt = 0;
while(cin >> n && n){
TSP = 0.0;
for(int i = 0; i < n;i++){
int x,y;
cin >> x >> y;
v.push_back({x,y});
}
for(int i = 0; i < n; i++){
int x1 = v[i].first;
int y1 = v[i].second;
for(int j = i+1; j < n; j++){
int x2 = v[j].first;
int y2 = v[j].second;
double D = sqrt(((x1-x2)*(x1-x2)) + ((y1-y2)*(y1-y2))) + 16.0;
graph[i][j] = D;
graph[j][i] = D;
// cerr << x1 << " "<<y1 << " "<<x2 << " "<<y2<<endl;
}
//cerr<<"\n";
}
//print();
double mn = 999999.0;
for(int i = 0; i < n; i++){
TSP = tsp(i, mn);
mn = min(TSP, mn);
}
cout << "**********************************************************\n";
cout << "Network #"<<++cnt<<"\n";
path_print();
cout <<"Number of feet of cable required is "<<fixed<<setprecision(2)<< mn<<".\n";
path.clear();
v.clear();
}
//double end_time = clock();
//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
return 0;
}
|
No comments:
Post a Comment