Advertisement
YEZAELP

SMMR-170: Salesman

Jun 28th, 2020
95
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.74 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 1e9;
  4. int n, Bit;
  5. int x[28],y[28];
  6. vector <vector<int>> dp(262153, vector<int>(28,INF));
  7. int distance(int i, int j){
  8.     return (x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]);
  9. }
  10. int salesman(int bit, int i){
  11.     if(bit == Bit) return distance(i,1);
  12.     if(dp[bit][i] != INF) return dp[bit][i];
  13.  
  14.     for(int j=1; j<=n; j++){
  15.         if(bit & (1<<(j-1)) ) continue;
  16.         dp[bit][i] = min(dp[bit][i], distance(i,j) + salesman(bit | (1<<(j-1)), j));
  17.     }
  18.     return dp[bit][i];
  19. }
  20. int main(){
  21.  
  22.     scanf("%d",&n);
  23.     for(int i=1; i<=n; i++){
  24.         scanf("%d%d",&x[i],&y[i]);
  25.     }
  26.     Bit = (1<<n) - 1;
  27.     printf("%d",salesman(1,1));
  28.  
  29.     return 0;
  30. }
Advertisement
RAW Paste Data Copied
Advertisement