さーじぇんとらいあん

DPで書いてみた。

問題文: Sergeant Rian | Aizu Online Judge

アホなDP解(メモ化)なので、0.5sくらいTLEします。

いちおう出力はただしいらしい(PCKオンライン講座で確認済み)

DPは何も考えずに目先のことだけ考えてれば解けるからいいけど、やはり性質を考えた上で貪欲法を適用するのがかしこい。

#include <iostream>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
#define INF (1<<15)
#define rep(i,n) for(int i = 0 ; i < n ; i++)
struct edge{
	int a,b,c,i;
	edge(int x,int y,int z,int I){a = x , b = y , c = z , i = I;}
	edge(){}
};

unsigned short n , m , dp[20][1<<19];
char done[20][1<<19];
int msk[20];
vector<edge> ee[20];

int dfs(int bit,int pos){
	if(bit == (1<<m)-1) return 0;
	if(dp[pos][bit] != 65535) return dp[pos][bit];

	if(done[pos][bit]) return INF;
	else done[pos][bit] = true;
	
	// 移動せず爆発した場合に、全部橋が潰れた状態になれば0がかえってきて、それ以外ならINFがかえってくる。
	int ans = dfs(bit | msk[pos] , pos);
	
	rep(i,ee[pos].size()){
		if( (bit >> ee[pos][i].i & 1 ) )continue ; //その橋が潰れてたらcontinue
		ans = min(ans, dfs(bit | msk[pos] , ee[pos][i].b) + ee[pos][i].c); // その島に繋がってる橋全部爆発して移動
		ans = min(ans, dfs(bit , ee[pos][i].b) + ee[pos][i].c); //爆発せず移動
	}
	
	return dp[pos][bit] = ans;
}
int main(){
	while(cin >> n && n){
		m = n-1;	
		rep(i,n)ee[i].clear();
		rep(i,m){
			int a,b,c;
			cin >> a >> b >> c;
			a--,b--;
			ee[a].push_back(edge(a,b,c,i));
			ee[b].push_back(edge(b,a,c,i));
		}
		rep(x,n){
			int mask = 0;
			rep(i,ee[x].size()) mask |= (1<<ee[x][i].i);
			msk[x] = mask;
		}
		memset(done,0,sizeof(done));
		memset(dp,-1,sizeof(dp));
		cout << dfs(0,0) << endl;
	}
}