fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const long long INF = 1e18;
  7.  
  8. int n;
  9. vector<int> start_state;
  10. vector<vector<int>> C;
  11.  
  12. signed main() {
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(nullptr);
  15.  
  16.     cin >> n;
  17.  
  18.     start_state.resize(n);
  19.     for (int i = 0; i < n; i++) cin >> start_state[i];
  20.  
  21.     C.assign(n, vector<int>(n));
  22.     for (int i = 0; i < n; i++) {
  23.         for (int j = 0; j < n; j++) {
  24.             cin >> C[i][j];
  25.         }
  26.     }
  27.  
  28.     vector<int> target = start_state;
  29.     sort(target.begin(), target.end());
  30.  
  31.     map<vector<int>, long long> dist;
  32.  
  33.     priority_queue<
  34.         pair<long long, vector<int>>,
  35.         vector<pair<long long, vector<int>>>,
  36.         greater<pair<long long, vector<int>>>
  37.     > pq;
  38.  
  39.     dist[start_state] = 0;
  40.     pq.push({0, start_state});
  41.  
  42.     while (!pq.empty()) {
  43.         auto [d, cur] = pq.top();
  44.         pq.pop();
  45.  
  46.         if (d != dist[cur]) continue;
  47.  
  48.         if (cur == target) {
  49.             cout << d << '\n';
  50.             return 0;
  51.         }
  52.  
  53.         for (int i = 0; i < n; i++) {
  54.             for (int j = i + 1; j < n; j++) {
  55.  
  56.                 vector<int> nxt = cur;
  57.                 swap(nxt[i], nxt[j]);
  58.  
  59.                 long long nd = d + C[i][j];
  60.  
  61.                 if (!dist.count(nxt) || nd < dist[nxt]) {
  62.                     dist[nxt] = nd;
  63.                     pq.push({nd, nxt});
  64.                 }
  65.             }
  66.         }
  67.     }
  68.  
  69.     return 0;
  70. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
6
1 2 3 4 6 5
0 1 2 3 4 5
1 0 1 2 3 4
2 1 0 1 2 3
3 2 1 0 1 2
4 3 2 1 0 901
5 4 3 2 901 0
stdout
copy 
4
https://ideone.com/u8ARhV
language:
C++14 (gcc 8.3)
created:
1 day 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!