AOJ 0235 - Sergeant Rian

問題文 : サージェント・ライアン

解法 :
最後に訪れる島を根とした木を作ると, 爆破する橋が必然的に決まる.
ゆえに, 全ての島について最後の島としたときの爆破する時間を考え, その最小値を答えとする.

コード :

#include <cstdio>
#include <cstring>
#include <vector>

#define INF (1 << 30)

using namespace std;

typedef struct {
	int par;
	vector<int> son;
} Node;

Node T[20];
int n;
int cost[20][20];
bool vis[20];
int cSum;

void makeTree(int v, int p)
{
	T[v].par = p;
	vis[v] = true;
	for (int i = 0; i < n; i++){
		if (vis[i] == false && cost[v][i] != INF){
			T[v].son.push_back(i);
			makeTree(i, v);
		}
	}
}

void dfs(int v, int c)
{
	vis[v] = true;
	if (T[v].son.size() == 0){
		return;
	}
	
	for (int i = 0; i < T[v].son.size(); i++){
		if (vis[T[v].son[i]] == false){
			dfs(T[v].son[i], cost[v][T[v].son[i]]);
		}
	}
	cSum += c * 2;
}

int bomb()
{
	cSum = 0;
	int pNode = 0;
	
	while (~pNode){
		dfs(pNode, 0);
		if (~T[pNode].par) cSum += cost[pNode][T[pNode].par];
		pNode = T[pNode].par;
	}
	
	return (cSum);
}

int main()
{
    int a, b, t;
    int res;
    
    while (scanf("%d", &n) && n){
		
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				cost[i][j] = INF;
			}
		}
        
        for (int i = 0; i < n - 1; i++){
            scanf("%d %d %d", &a, &b, &t);
            cost[a - 1][b - 1] = cost[b - 1][a - 1] = t;
        }
        
        res = INF;
		
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++) T[j].son.clear();
			memset(vis, false, sizeof(vis));
			makeTree(i, -1);
			memset(vis, false, sizeof(vis));
			res = min(res, bomb());
		}
		
        printf("%d\n", res);
    }
    
    return (0);
}