Tamflexの貯蔵庫

やる気のない備忘録

aoj DPL_2_A

Traveling Salesman Problem | Aizu Online Judge


巡回セールスマンの問題
bit dpを使う問題
bit列にした時1を訪れていない頂点, 0を訪れた頂点としてdpを用いる.
計算量はO(n^2*2^n)

int n;
int d[15][15];
int dp[1<<15][15];

void solve()
{
  REP(i,(1<<n)) fill_n(dp[i],n,INF);
  dp[(1<<n)-1][0] = 0;
  DOWN(i,(1<<n)-2,0) REP(v,n) REP(u,n) if(!(i>>u&1))
    dp[i][v] = min(dp[i][v],dp[i|1<<u][u]+d[v][u]);
}

int main()
{
  int m; cin >> n >> m;
  REP(i,15) fill_n(d[i],15,INF);
  REP(i,m)
  {
    int s,t,c; cin >> s >> t >> c;
    d[s][t] = c;
  }
  solve();
  cout << (dp[0][0]==INF?-1:dp[0][0]) << endl;
  return 0;
}