ccbeginner

UVa Q10911 (DFS)

Jan 19th, 2020
137
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q10911
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int arr[16][2];
  6. double dist(int p, int q){
  7.     return sqrt((arr[p][0]-arr[q][0]) * (arr[p][0]-arr[q][0]) + (arr[p][1]-arr[q][1]) * (arr[p][1]-arr[q][1]));
  8. }
  9.  
  10. bool vis[16];
  11. double ans, len;
  12. int n;
  13. void dfs(int depth){
  14.     if(len >= ans)return;
  15.     if(depth == n){
  16.         ans = len;
  17.     }else{
  18.         int one, two;
  19.         for(int i = 0; i < n*2; ++i){
  20.             if(!vis[i]){
  21.                 one = i;
  22.                 vis[one] = 1;
  23.                 break;
  24.             }
  25.         }
  26.         for(int i = one+1; i < n*2; ++i){
  27.             if(!vis[i]){
  28.                 two = i;
  29.                 len += dist(one, two);
  30.                 vis[two] = 1;
  31.                 dfs(depth+1);
  32.                 vis[two] = 0;
  33.                 len -= dist(one, two);
  34.             }
  35.         }
  36.         vis[one] = 0;
  37.     }
  38. }
  39.  
  40. int32_t main(){
  41.     string aux;
  42.     int cnt = 0;
  43.     while(cin >> n){
  44.         if(n == 0)break;
  45.         ans = INT_MAX;
  46.         len = 0;
  47.         memset(vis, 0, sizeof(vis));
  48.         for(int i = 0; i < n*2; ++i){
  49.             cin >> aux >> arr[i][0] >> arr[i][1];
  50.         }
  51.         dfs(0);
  52.         printf("Case %d: %.2f\n", ++cnt, ans);
  53.     }
  54.     return 0;
  55. }
RAW Paste Data