#include <stdio.h>
//#define MAX_N 1000
#define MAX_N 10
#define MAX_LEN 2000000000000 //a와 b사이 최대로 나올수있는 max 거리값. 10^6*10^6 + 10^6*10^6
#define LEN(a,b) ((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]))*E
int N;
int visited[MAX_N]; //visited값 저장
double len[MAX_N]; //비교하는 length값 저장.
unsigned long long int x[MAX_N]; //x좌표 저장
unsigned long long int y[MAX_N]; //y좌표 저장
double E;//e값 저장
int main(void) {
freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);
for (int t = 1; t <= T; t++) {
scanf("%d", &N); //좌표 개수
for (int i = 0; i < N; i++) {
scanf("%d", &x[i]); //x좌표 입력
}
for (int j = 0; j < N; j++) {
scanf("%d", &y[j]); //y 좌표 입력
len[j] = MAX_LEN; //len배열 좌표를 최대값으로 초기화
}
scanf("%lf", &E); //E값 입력
for (int i = 0; i < N; i++)
visited[i] = 0; //visited값 초기화
//시작점
int v = 0;
visited[v] = 1;
double ans_m = 0;
for (int k = 0; k < N - 1; k++) {
double min = MAX_LEN + 1; //min_distance값을 최대거리+1값으로 초기화. 최초에 무조건 치환될 수 있게하기위함.
int min_num = 0;
for (int i = 1; i < N; i++) {
if (visited[i])continue; //방문한 곳이면 pass
if (len[i] > LEN(v, i)) { //방문하지않았으면서, i-v사이 거리가 max로 차기화된 len[i]값보다 작은경우,
len[i] = LEN(v, i); //더 작은 LEN값을 len[i]에 저장
}
if (min>len[i]) { //min값이 len[i]값보다 크면
min = len[i]; //min값 치환
min_num = i; //i값을 min_num에 업데이트
}
}
v = min_num; //발견된 현재 노드와 가장 짧은 거리를 가진 min_num값을 v에 입력하고
visited[v] = 1;//v를 visit처리.
ans_m += min;//결과값에 min값 더하기.
}
printf("#%d %.0lf\n", t, ans_m);
}
}
댓글