[백준/BOJ] 백준 12784번 : 인하니카 공화국

[백준/BOJ] 백준 12784번 : 인하니카 공화국

https://www.acmicpc.net/problem/12784

1번 노드가 루트인 트리를 만들고 리프 노드와 연결을 끊는 최소 비용을 구해서 문제를 해결했다.

코드

#include #include #include using namespace std; int tc; int n, m; vector> adj[1001]; //(다이너마이트 수, 목적지) vector maked(1001); vector> children[1001]; //(다이너마이트 수, 자식노드) void Pre() { for (int i = 0; i < 1001; i++) { adj[i].clear(); maked[i] = 0; children[i].clear(); } } //here노드가 루트인 트리 만들기 void MakeTree(int here) { maked[here] = 1; for (int i = 0; i < adj[here].size(); i++) { int there = adj[here][i].second; int this_cost = adj[here][i].first; if (maked[there] == 0) { children[here].push_back(make_pair(this_cost, there)); MakeTree(there); } } } //here이 루트인 서브트리에서 리프노드와 연결을 끝는 최소 비용을 구한다 int Solve(int here) { //here이 리프노드일때 if (children[here].size() == 0) return 987654321; int ret = 0; for (int i = 0; i < children[here].size(); i++) { int there = children[here][i].second; int this_cost = children[here][i].first; ret += min(this_cost, Solve(there)); } return ret; } int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> tc; for (int t = 0; t < tc; t++) { Pre(); cin >> n >> m; if (n == 1) { cout << 0 << "

"; continue; } for (int i = 0; i < m; i++) { int u, v, d; cin >> u >> v >> d; adj[u].push_back(make_pair(d, v)); adj[v].push_back(make_pair(d, u)); } MakeTree(1); cout << Solve(1) << "

"; } return 0; }

from http://geniusjo-story.tistory.com/532 by ccl(A) rewrite - 2021-11-20 15:01:09