yusuke
5/9/2020 - 12:58 AM

bitDP

constexpr LL kInf = 1e18;

typedef tuple<LL, int, int> P;  // dist, S, v
struct Edge {
  int to;
  LL dist;
  Edge(int a, LL b) : to(a), dist(b) {}
};

vector<vector<LL>> tsp(const vector<vector<Edge>>& G){
  const int V = G.size();
  vector<vector<LL>> d(1<<V, vector<LL>(V, kInf));
  d[0][0]=0;

  priority_queue<P,vector<P>,greater<P>> que;
  que.push(P(0, 0, 0));

  while(!que.empty()){
    LL dist; int S, v;
    tie(dist, S, v) = que.top(); que.pop();

    if (d[S][v] < dist) continue;
    for (const auto& e : G[v]) {
      int u = e.to;
      int nextS = S | (1<<u);
      if (S == nextS) continue;

      int next_dist = dist + e.dist;
      if (d[nextS][u] > next_dist) {
        d[nextS][u] = next_dist;
        que.push(P(next_dist, nextS, u));
      }
    }
  }

  return d;
}
int main(){
  int V, E; cin >> V >> E;
  vector<vector<Edge>> G(V);
  const int kFinishS = (1 << V) - 1;
  for (int i = 0; i < E; ++i) {
    int s, t, d; cin >> s >> t >> d;
    G[s].push_back(Edge(t, d));
  }

  auto d = tsp(G);
  LL ans = d[kFinishS][0];
  if (ans == kInf) cout << -1 << endl;
  else             cout << ans << endl;

  return 0;
}