[ACM] Solution-Q216: Getting in Line

Thinking:

害我WA了一次, 第二次就AC了

Solution:

[c]
/* @file 216.c
* @date 10/17/2010
* @version v0.01
* @author "TXShon" <txshon@gmail.com>
* @note CreativeCommons(cc) 2010 TXShon, cc by-nc-nd
*
*Description
* Acm practice using c
*History
*/
#include <stdio.h>
#include <math.h>

int n, time[8], temp[8], map[8][2], ans[8];
double k[8], r[8], max, tempp;

int dfs(int a, int b){
int i, j;
if(n==b){
i = 0;
while(a!=-2){
temp[i] = a;
a=time[a]-1;
i++;
}
for( i=0; i<n-1; i++){
k[i]=pow(pow((map[temp[i]][0]-map[temp[i+1]][0]), 2)+pow((map[temp[i]][1]-map[temp[i+1]][1]), 2), .5);
}
tempp =0;
for( i=0; i<n-1; i++){
tempp+=k[i];
}
if(tempp<=max){
max=tempp;
for( i=0; i<n-1; i++){
ans[i] = temp[i];
r[i] = k[i];
}
ans[n-1] = temp[n-1];
}
return ;
}
for(i=0; i<n; i++){
if(!time[i]){
time[i]=a+1;
dfs( i, b+1);
time[i]=0;
}
}
return 0;
}

int main()
{
int i, z;

z = 0;

while(scanf("%d", &n)==1){
if(!n)break;
for( i=0; i<n; i++){
scanf("%d%d", &map[i][0], &map[i][1]);
time[i] = 0;
}
max = 100000000;
dfs( -2, 0);
printf("**********************************************************\nNetwork #%d\n", z+1);
for( i=0; i<n-1; i++){
printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n", map[ans[i]][0], map[ans[i]][1], map[ans[i+1]][0], map[ans[i+1]][1], r[i]+16);
}
printf("Number of feet of cable required is %.2lf.\n", max+16*(n-1));
z++;
}

return 0;
}

[/c]