AOJ2254 最短ルート

解法

---

bitでいろいろやるのは自明っぽかったので察して、
Dijkstraじゃね？って思ったがMLEで詰んでいた。
動的計画法らしかったのでそうした。
bit[クリアしてるかの状態] = 最短時間

ソース

---

#include<iostream>
#include<algorithm>
using namespace std;
#define INF ( 1 << 30 )
int N,mas[16][17],dp[1<<17];
 
int rec(int bit){
  if(dp[bit]) return dp[bit];
  if(!bit) return 0;
 
  int ret = INF;
  for(int i = 0 ; i < N ; i++ ){
    if(!(bit & (1 << i))) continue;
    int min_cost = mas[i][0];
    for(int j = 0 ; j < N ; j++ ){
      if(i != j && !(bit & (1 << j))) min_cost = min( min_cost, mas[i][j+1]);
    }
    ret = min( ret, min_cost + rec(bit&~(1 << i)));
  }
  return dp[bit] = ret;
}
 
int main(){
  while(cin >> N , N ){
    fill_n( dp, 1<<17, 0);
    for(int i = 0 ; i < N ; i++ ){
      for(int j = 0 ; j <= N ; j++ ){
        cin >> mas[i][j];
      }
    }
    cout << rec((1 << N)-1) << endl;
  }
}

ループ

#include<cstdio>
#include<algorithm>
using namespace std;
#define INF ( 1 << 25 )
int N,mas[16][17],dp[1<<16];
int solve(){
  for(int i = 0 ; i < 1 << N ; i++ ) dp[i] = INF;
  dp[(1 << N) - 1] = 0;
  for(int bit = (1 << N) - 1 ; bit >= 0 ; bit-- ){
    for(int i = 0 ; i < N ; i++ ){
      if(!(bit & (1 << i))) continue;
      int min_cost = mas[i][0];
      for(int j = 0 ; j < N ; j++ ){
        if(!(bit & (1 << j))) min_cost = min( min_cost, mas[i][j+1]);
      }
      dp[bit&~(1<<i)] = min(dp[bit&~(1<<i)],min_cost + dp[bit]);
    }
  }
  return dp[0];
}
int main(){
  while(scanf("%d",&N), N ){
    for(int i = 0 ; i < N ; i++ ){
      for(int j = 0 ; j <= N ; j++ ){
        scanf("%d",&mas[i][j]);
      }
    }
    printf("%d\n",solve());
  }
}

最初浮かんだ解法,Dijjkstraは状態数が多すぎた。
used[16][1<<16] = used[今の場所][bit]。今の場所が不要なことを察したかった。
上のDPと似てるけど修正したやつ。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define fr first
#define sc second
#define INF ( 1 << 30 )
typedef pair < int , int > P;
int N, cost[16][17];
bool used[1<<16];
int Dijkstra(){
  priority_queue< P , vector<P> , greater<P> > que;
  for(int i = 0 ; i < N ; i++ ){
    que.push(P(cost[i][0],((1<<N)-1)&~(1<<i)));
  }
  fill_n( used, 1<<16, false);
  while(!que.empty()){
    P p = que.top();
    que.pop();
    if(p.sc == 0) return p.fr;
    if(used[p.sc]++) continue;
    for(int i = 0 ; i < N ; i++ ){
      if(!((p.sc >> i) & 1)) continue;
      int ret = cost[i][0];
      for(int j = 0 ; j < N ; j++ ){
        if(i != j && !((p.sc >> j) & 1)) ret = min(ret, cost[i][j+1]);
      }
      que.push(P(p.fr+ret,p.sc&~(1 << i)));
    }
  }
  return -1;
}
int main(){
  while(cin >> N , N){
    for(int i = 0 ; i < N ; i++ ){
      for(int j = 0 ; j <= N ; j++ ){
        cin >> cost[i][j];
      }
    }
    cout << Dijkstra() << endl;
  }
}