UVA216 Getting in Line

Graph

출처: UVA UVA216 Getting in Line


SOL)
방문 할 수 있는 경우를 모두 구하여 각각의 경우 가장 짧은 값을 갖는 것을 선택 후 출력.
graph라 하기도 애매하다..
[-] Collapse

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int Num, cnt = 0;
struct info{
    int x;
    int y;
};
int arr[8];
int visit[8];
info v[9];
int adj[9][9];
double result;
double temp;
void init(){
    result = 1234567890;
    for (int i = 0; i < Num; i++){
        arr[i] = i + 1;
        scanf("%d%d", &v[i + 1].x, &v[i + 1].y);
    }
}
double dis(int l, int r){
    double x1 = (double)v[l].x;
    double x2 = (double)v[r].x;
    double y1 = (double)v[l].y;
    double y2 = (double)v[r].y;
    return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}
void search(int idx){
    if (idx == Num - 1)
        return;
    temp += dis(arr[idx], arr[idx + 1]) + double(16);
    search(idx + 1);
}

int main(){
    //freopen("input.txt", "r", stdin);
    double x = 532.29;
    double y = 3.23;
    while (1){
        scanf("%d", &Num);
        if (Num == 0) break;
        cnt++;
        init();
        do{
            temp = 0;
            search(0);
            if (result > temp){
                result = temp;
                for (int i = 0; i < Num; i++)
                    visit[i] = arr[i];
            }
        } while (next_permutation(arr, arr + Num));
        printf("**********************************************************\n");
        printf("Network #%d\n", cnt);
        for (int i = 0; i < Num - 1; i++){
            printf("Cable requirement to connect ");
            printf("(%d,%d) ", v[visit[i]].x, v[visit[i]].y);
            printf("to (%d,%d) ",v[visit[i + 1]].x, v[visit[i + 1]].y);
            printf("is %.2f feet.\n", dis(visit[i], visit[i+1]) + double(16));
        }
        printf("Number of feet of cable required is ");
        printf("%.2f.\n", result);
    }
    return 0;
}