Problem 2254 Fastest Route ICPC模擬国内予選2011 C

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2254

解き方

頂点数が16以下なので、ビットDPで解ける。
int s;で (0000...0000)2の各ビットを頂点に対応させ訪れたかどうかの情報を保持させる。
s == 1 == (0000...0001)2なら、1つ目の頂点を訪れて他は訪れていない。
s == 2 == (0000...0010)2なら、2つ目
s == 3 == (0000...0011)2なら、1つ目と2つ目

頂点数を仮に5とすると全て訪れている状態は
s == (0000...011111)2 = 31 == (1<<5)-1

ソースコード

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long int ll;
#define FOREACH(t,p,it) for(t::iterator it=p.begin();it!=p.end();++it)
#define foreach(t,p) FOREACH(t,p)
#define all(p) p.begin(),p.end()
#define REP(i,n) for(ll i=0;i<n;i++)
#define rep(p) REP(i,p)
const ll INF = 10000000LL;
const int MX = 16;
int times[MX][MX+1];
int dp[1<<MX];
int n;

int solve(int s)
{
    if( dp[s] ) return dp[s];
    if( s == (1<<n)-1 ) return dp[s]=0;
    ll sum = INF, cache;
    REP(i,n) { if(s>>i&1) continue;    sum=min(sum,(cache=solve(s|1<<i))+times[i][0]);
    REP(t,n) { if(!(s>>t&1)) continue; sum=min(sum,cache+times[i][t+1]); }}

    return dp[s]=sum;
}

int main()
{
    while(cin>>n&&n)
    {
        REP(i,1<<n) dp[i]=0;
        REP(i,n) REP(t,n+1) cin>>times[i][t];
        cout << solve(0) << endl;
    }

    return 0;
}