AOJ : Fastest Route

問題リンク:Fastest Route | Aizu Online Judge

問題概要：
N個のステージを全てクリアするためにかかる最小の時間をもとめろ
(1 <= N <= 16)

使用した言語：C＋＋

解法1：
bitで状態を管理しdequeをつかってdfsもどきをした
mincost[(1<<17)-1]というint型の配列を最小時間保存用として確保し、
bitが立っているならばそのステージはクリアしたものとした
dequeには最初何も武器を持たない状態で各ステージをクリアした状態をいれる
その後、bfsで最小時間をもとめる
が、bfsだとTLEをくらうのでdequeに要素を入れる順番をbackではなくfrontにする
こうすることでdfsっぽくできるので
(これまでで分かっている全面クリアに要する最小時間)　<= （今かかっているコスト）
という枝刈りが有効になる

解法2；
ビットDPをする
int dp[(1<<17)] という配列を用意し、

for i ０から(1<<(N+1))-2
　for j 1からNまで
　　if まだ状態 i がステージ j を訪れていないなら
　　　for k 0からNまで
　　　　if kが０、または状態 i がステージ k をクリアしているならば
　　　　　dp[i|(1<

#include<iostream>
#include<deque>
#include<algorithm>
#include<bitset>
#include<vector>
#include<cassert>
#define F first
#define S second

using namespace std;

class Pox
{
public:
  int visited;
  int cost;
  Pox(int visited = 0,int cost = 0):visited(visited),cost(cost){}
};
 
int main()
{ 
 
  short N;
  while(cin >> N,N)
    {
      int G[N+1][N+1];
      
      for(int i=1;i<=N;i++)
	{
	  for(int j=0;j<=N;j++)
	    {
	      cin >> G[i][j];
	    }
	}
         
      int mincost[(1<<17)-1];   
      for(int i=0;i< ((1<<17)-1) ;i++)
	mincost[i] = (1<<26);
      
      deque<Pox> deq;
      for(int i=1;i<=N;i++)
	{
	  deq.push_back(Pox((1<<i),G[i][0]));
	  mincost[(1<<i)] = G[i][0];
	}
       
 
      int ans = (1<<29);
      while(!deq.empty())
	{
	  Pox pox = deq.front(); deq.pop_front();
	  int visited = pox.visited;
	  int cost = pox.cost;	  
	  
	  if(ans <= cost)
	    continue;
	  
	  if(visited == (1<<(N+1))-2)
	    {
	      ans = min(ans,cost);
	      continue;
	    }
	  
	  for(int i=1;i<=N;i++)
	    {
	      if((visited>>i)&1)
		continue;
	      
	      for(int j=0;j<=N;j++)
		{
		  if(j == 0 || ( (visited>>j)&1 ))
		    {
		      int nvisited = visited|(1<<i);
		      if(mincost[nvisited] > cost + G[i][j])
			{
			  mincost[nvisited] = cost + G[i][j];
			  deq.push_front(Pox(nvisited,cost+G[i][j]));
			}
		    }
		}
	            
	    }
		  
	}
 
      cout << ans << endl;
 
    }
  return 0;
}

コード２(ビットDP)：

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
  int N;
  while(cin >> N,N)
    {
      int G[N+1][N+1];
      for(int i=1;i<=N;i++)
	for(int j=0;j<=N;j++)
	  cin >> G[i][j];

      int dp[(1<<17)];
      for(int i=0;i<(1<<17);i++)
	dp[i] = (1<<29);

      dp[0] = 0;

      for(int i=0;i<=(1<<(N+1))-2;i++)
	for(int j=1;j<=N;j++)
	  if(!((i>>j)&1))
	    for(int k=0;k<=N;k++)	      
	      if(k == 0 || ( (i>>k)&1 ))
		dp[i|(1<<j)] = min(dp[i|(1<<j)],dp[i]+G[j][k]);
      cout << dp[(1<<(N+1))-2] << endl;
    }
  return 0;
}