UVa216
1671 ワード
純粋な列挙
すべての配列を列挙し、最小距離を記録します.
しかし、単一ソースの最短パスアルゴリズムがあるようです.
すべての配列を列挙し、最小距離を記録します.
しかし、単一ソースの最短パスアルゴリズムがあるようです.
#include<stdio.h>
#include<math.h>
#define Maxnode 9
#define INF 100000
int ans[Maxnode];
int a[Maxnode];
double distance[Maxnode],ansdistance[Maxnode];
int nodes;
double maxdist;
struct node{
int x,y;
}vector[Maxnode];
void dfs(int cur){
int i,ok,j;
double xdis,ydis,dist,total_dis;
if(cur==nodes+1){
for(i=1,total_dis=0;i<nodes;i++){
xdis=vector[a[i]].x-vector[a[i+1]].x;
ydis=vector[a[i]].y-vector[a[i+1]].y;
dist=sqrt(xdis*xdis+ydis*ydis);
distance[i]=dist=dist+16;
total_dis +=dist;
}
if(total_dis<maxdist){
maxdist=total_dis;
for(i=1;i<=nodes;i++){
ans[i]=a[i];
}
for(i=1;i<nodes;i++){
ansdistance[i]=distance[i];
}
}
return ;
}
else{ //
for(i=1;i<=nodes;i++){
ok=1;
a[cur]=i;
for(j=1;j<cur;j++){
if(a[j]==a[cur]){
ok=0;
break;
}
}
if(ok)
dfs(cur+1);
}
}
}
int main()
{
int i,case_num=1;
while(scanf("%d",&nodes)!=EOF&&nodes){
maxdist=INF;
for(i=1;i<=nodes;i++){
scanf("%d %d",&vector[i].x,&vector[i].y);
}
dfs(1);
printf("**********************************************************
");
printf("Network #%d
",case_num);
for(i=1;i<nodes;i++){
printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.
",vector[ans[i]].x,vector[ans[i]].y,vector[ans[i+1]].x,vector[ans[i+1]].y,ansdistance[i]);
}
printf("Number of feet of cable required is %.2f.
",maxdist);
case_num++;
}
return 0;
}