fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int Nmax = 2e6 + 7;
  5. const int MOD = 1000000007;
  6.  
  7. int numnode, numedge;
  8. vector<pair<int, int>> adj[Nmax];
  9. long long dp[23][Nmax];
  10. pair<int, int> trace[23][Nmax];
  11. void in(){
  12.     memset(dp, -1, sizeof(dp));
  13.     cin >> numnode >> numedge;
  14.     for(int i = 1; i <= numedge; i++){
  15.         int u, v, c;
  16.         cin >> u >> v >> c;
  17.         adj[u].push_back({c, v});
  18.     }
  19. }
  20. long long calc(int u, int choose){
  21.     if(choose == (1 << numnode) - 1){
  22.         long long res = 2e18;
  23.         for(auto e : adj[u]){
  24.             int c = e.first, v = e.second;
  25.             if(v == 1){
  26.                 res = min(res, 0ll + c);
  27.             }
  28.         } return res;
  29.     }
  30.     long long &res = dp[u][choose];
  31.     if(res != -1) return res;
  32.     res = 1e18;
  33.     for(auto e : adj[u]){
  34.         int c = e.first, v = e.second;
  35.         if(!((choose >> (v - 1)) & 1)) {
  36.             if(res > 0ll + c + calc(v, choose + (1 << (v - 1)))){
  37.                 res = 0ll + c + calc(v, choose + (1 << (v - 1)));
  38.                 trace[u][choose] = {v, choose + (1 << (v - 1))};
  39.             }
  40.         }
  41.     }
  42.     return res;
  43. }
  44. void sol(){
  45.     cout << calc(1, 1);
  46.     cout << '\n';
  47.     pair<int, int> t = {1, 1};
  48.     while(1){
  49.         cout << t.first << ' ';
  50.         t = trace[t.first][t.second];
  51.         if(t.second == 0) break;
  52.     }
  53. }
  54. int main(){
  55.     freopen("TSP.inp", "r", stdin);
  56.     freopen("TSP.out", "w", stdout);
  57.     ios_base::sync_with_stdio(false);
  58.     cin.tie(0);
  59.     int t = 1;
  60.     //cin >> t;
  61.     while(t--){
  62.        in();
  63.        sol();
  64.     }
  65.     return 0;
  66. }
Success #stdin #stdout 0.16s 410112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nawL3I
language:
C++ (gcc 8.3)
created:
326 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!