fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_N = 1000;
  5. const string INPUT_FILE = "dulich14.inp";
  6. const string OUTPUT_FILE = "dulich14.out";
  7.  
  8. int N, M, minCost;
  9. vector<vector<int>> adj(MAX_N + 1);
  10. vector<vector<int>> weight(MAX_N + 1, vector<int>(MAX_N + 1, 0));
  11. vector<bool> visited(MAX_N + 1, true);
  12. vector<int> path(MAX_N + 1), bestPath(MAX_N + 1), cost(MAX_N + 1);
  13.  
  14. void addEdge(int u, int v, int c) {
  15.     adj[u].push_back(v);
  16.     adj[v].push_back(u);
  17.     weight[u][v] = c;
  18.     weight[v][u] = c;
  19. }
  20.  
  21. void readInput() {
  22.     cin >> N >> M;
  23.     for (int i = 0; i < M; i++) {
  24.         int u, v, c;
  25.         cin >> u >> v >> c;
  26.         addEdge(u, v, c);
  27.     }
  28. }
  29.  
  30. void updateBestPath() {
  31.     int totalCost = cost[N] + weight[path[N]][path[1]];
  32.     if (totalCost < minCost) {
  33.         minCost = totalCost;
  34.         bestPath = path;
  35.     }
  36. }
  37.  
  38. void findHamiltonianCycle(int i) {
  39.     for (int j : adj[path[i - 1]]) {
  40.         if (visited[j] && weight[path[i - 1]][j] > 0) {
  41.             path[i] = j;
  42.             cost[i] = cost[i - 1] + weight[path[i - 1]][j];
  43.  
  44.             if (cost[i] < minCost) {
  45.                 if (i < N) {
  46.                     visited[j] = false;
  47.                     findHamiltonianCycle(i + 1);
  48.                     visited[j] = true;
  49.                 } else if (weight[j][path[1]] > 0) {
  50.                     updateBestPath();
  51.                 }
  52.             }
  53.         }
  54.     }
  55. }
  56.  
  57. void printResult() {
  58.     if (minCost == INT_MAX) {
  59.         cout << "-1\n";
  60.     } else {
  61.         cout << minCost << "\n";
  62.     }
  63. }
  64.  
  65. int main() {
  66.     freopen(INPUT_FILE.c_str(), "r", stdin);
  67.     freopen(OUTPUT_FILE.c_str(), "w", stdout);
  68.  
  69.     readInput();
  70.     path[1] = 1;
  71.     cost[1] = 0;
  72.     visited[1] = false;
  73.     minCost = INT_MAX;
  74.  
  75.     findHamiltonianCycle(2);
  76.     printResult();
  77.  
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 6952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3i8C0l
language:
C++ (gcc 8.3)
created:
3 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!