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 0から(1<<(N+1))-2
for j 1からNまで
if まだ状態 i がステージ j を訪れていないなら
for k 0からNまで
if kが0、または状態 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; }
コード2(ビット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; }