Cod sursa(job #2141174)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 24 februarie 2018 10:53:43
Problema Ciclu hamiltonian de cost minim Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <memory.h>

using namespace std;

const int maxn = 18;
const int inf = 0x3f3f3f3f;

vector <pair<int, int>> g[maxn], gt[maxn];
int n, m, dp[1 << maxn][maxn];

int main() {
  ifstream fin("hamilton.in");
  ofstream fout("hamilton.out");

  fin >> n >> m;

  for(int i = 0; i < m; ++ i) {
    int x, y, z;
    fin >> x >> y >> z;
    g[x].push_back(make_pair(y, z));
    gt[y].push_back(make_pair(x, z));
  }

  memset(dp, inf, sizeof(dp));

  // conf
  dp[1][0] = 0;

  for(int conf = 2; conf < (1 << n); ++ conf) {
    for(int i = 0; i < n; ++ i) {
      if(conf & (1 << i)) {
        for(auto e : gt[i]) {
          if(conf & (1 << e.first)) {
            dp[conf][i] = min(dp[conf][i],
                dp[conf ^ (1 << i)][e.first] + e.second);
          }
        }
      }
    }
  }
  int sol = inf;

  // (conf, i)

  for(auto e : gt[0]) {
    sol = min(sol, dp[(1 << n) - 1][e.first] + e.second);
  }

  fout << sol << '\n';
}