코드 복사/붙여넣기 하는 당신이 아름답습니다.

12784 : 인하니카 공화국

풀이

루트부터 내려가서 자식들을 끊는 게 좋을지 부모를 끊는 게 좋을지 봐보자.

코드

#include <cstdio>
#include <vector>
using namespace std;

struct edg { int idx, dst; };
vector<edg> gph[1001];

int dfs(int prv, int now, int dst) {
	int ret = 0;
	for (edg nxt : gph[now]) if (prv != nxt.idx)
		ret += dfs(now, nxt.idx, nxt.dst);
	if (!ret) ret = dst;
	return ret < dst ? ret : dst;
}

int main() {
	int tc, n, m;
	for (scanf("%d", &tc); tc--;) {
		scanf("%d %d", &n, &m);
		for (int i = 0, u, v, w; i < m; i++) {
			scanf("%d %d %d", &u, &v, &w);
			gph[u].push_back({ v,w });
			gph[v].push_back({ u,w });
		}
		printf("%d\n", m ? dfs(0, 1, 1e9) : 0);
		for (int i = 0; i <= n; i++) gph[i].resize(0);
	}

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-03-30 16:06

Read more posts by this author