close

題目連結:   https://onlinejudge.org/external/2/216.pdf

題目大意:  問每個點到點總路徑最短多長。並記錄那個路徑

思路:  TSP問題,n = 8,可以直接枚舉 N! 解。用 STL next_permutation. 直接排列組合 代碼簡潔。用一個陣列紀錄最佳排列組合。

代碼:  

#include <bits/stdc++.h>
using namespace std;

int o[10], x[10], y[10], ans[10];
int main()
{
    //freopen("out.txt", "w", stdout);
    int n, cas = 1;
    while(cin >> n, n){
        for(int i = 0; i < n; ++i)
            cin >> x[i] >> y[i], o[i] = i;

        double mn = 1e9;
        do{
            double sum = 0;
            for(int i = 1; i < n; ++i){
                sum += (sqrt(pow(x[o[i]]-x[o[i-1]],2.0)+pow(y[o[i]]-y[o[i-1]],2.0))+16.0);
            }
            if(sum < mn) memcpy(ans, o, sizeof o), mn = sum;
        }while(next_permutation(o, o+n));

        puts("**********************************************************");
        printf("Network #%d\n", cas++);
        for(int i = 1; i < n; ++i){
            double dis = sqrt(pow(x[ans[i]]-x[ans[i-1]],2.0)+pow(y[ans[i]]-y[ans[i-1]],2.0))+16.0;
            printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.\n", x[ans[i-1]], y[ans[i-1]],
                   x[ans[i]], y[ans[i]], dis);
        }
        printf("Number of feet of cable required is %.2f.\n", mn);
    }
    return 0;
}

arrow
arrow
    創作者介紹
    創作者 尾玉 的頭像
    尾玉

    louisfghbvc的部落格

    尾玉 發表在 痞客邦 留言(0) 人氣()