fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Point {
  5.     double x, y;
  6. };
  7.  
  8. inline double dist(const Point &a, const Point &b) {
  9.     return hypot(a.x - b.x, a.y - b.y);
  10. }
  11.  
  12. struct MDMTSP {
  13.     int n, m;
  14.     vector<Point> pts;
  15.     vector<vector<double>> d;
  16.  
  17.     MDMTSP(int n, int m) : n(n), m(m), pts(n) {
  18.         d.assign(n, vector<double>(n, 0));
  19.     }
  20.  
  21.     void set_point(int i, double x, double y) {
  22.         pts[i] = {x, y};
  23.     }
  24.  
  25.     void build_dist() {
  26.         for (int i = 0; i < n; i++) {
  27.             for (int j = 0; j < n; j++) {
  28.                 d[i][j] = dist(pts[i], pts[j]);
  29.             }
  30.         }
  31.     }
  32.  
  33.     double best_cost = 1e18;
  34.     vector<int> best_assignment; // 각 salesman에게 몇 개씩 배정했는지
  35.  
  36.     void dfs(int idx, int left, vector<int>& assign) {
  37.         if (idx == m) {
  38.             if (left == 0) {
  39.                 // assign대로 route 구성
  40.                 int cur = 1;
  41.                 double total_cost = 0;
  42.                 for (int k = 0; k < m; k++) {
  43.                     double cost = 0;
  44.                     int prev = 0; // depot
  45.                     for (int j = 0; j < assign[k]; j++, cur++) {
  46.                         cost += d[prev][cur];
  47.                         prev = cur;
  48.                     }
  49.                     cost += d[prev][0];
  50.                     total_cost += cost;
  51.                 }
  52.                 if (total_cost < best_cost) {
  53.                     best_cost = total_cost;
  54.                     best_assignment = assign;
  55.                 }
  56.             }
  57.             return;
  58.         }
  59.         for (int take = 0; take <= left; take++) {
  60.             assign[idx] = take;
  61.             dfs(idx + 1, left - take, assign);
  62.         }
  63.     }
  64.  
  65.     void solve_and_print() {
  66.         vector<int> assign(m, 0);
  67.         dfs(0, n - 1, assign);
  68.  
  69.         // best_assignment에 따라 실제 노드 나눠서 출력
  70.         int cur = 1;
  71.         for (int k = 0; k < m; k++) {
  72.             for (int j = 0; j < best_assignment[k]; j++, cur++) {
  73.                 cout << cur << " ";
  74.             }
  75.             cout << "0\n";
  76.         }
  77.     }
  78. };
  79.  
  80. int main() {
  81.     ios::sync_with_stdio(false);
  82.     cin.tie(nullptr);
  83.  
  84.     int n, m;
  85.     cin >> n >> m;
  86.     MDMTSP solver(n, m);
  87.     for (int i = 0; i < n; i++) {
  88.         double x, y;
  89.         cin >> x >> y;
  90.         solver.set_point(i, x, y);
  91.     }
  92.     solver.build_dist();
  93.  
  94.     solver.solve_and_print();
  95. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
3 2
0 0
3 0
3 1
stdout 
0
1 2 0
https://ideone.com/5WWLUE
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!