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; } }