Source code for submission s596

fr.cpp

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dfs(int c, int f, int s, const vector < vector < pair <int, int> > > &g, vector <int> &mem) {
  5.  
  6. 	if ( mem[c] != -1 )
  7. 		return mem[c];
  8.  
  9. 	int n = 0;
  10.  
  11. 		for ( size_t i = 0; i < g[c].size(); ++i ) {
  12.  
  13. 			if ( f == g[c][i].first )
  14. 				continue;
  15.  
  16. 			n += dfs(g[c][i].first, c, g[c][i].second, g, mem);
  17.  
  18. 		}
  19.  
  20. 		if ( n == 0 )
  21. 			mem[c] = s;
  22. 		else
  23. 			mem[c] = min(n, s);
  24.  
  25. 	return mem[c];
  26.  
  27. }
  28.  
  29. int main() {
  30.  
  31. 	int n, c;
  32. 	while ( scanf("%d %d", &n, &c) == 2 ) {
  33.  
  34. 		--c;
  35.  
  36. 		vector < vector < pair <int, int> > > g(n);
  37. 		vector <int> mem(n, -1);
  38.  
  39. 		for ( int i = 0; i < n-1; ++i ) {
  40.  
  41. 			int a, b, c;
  42. 			scanf("%d %d %d", &a, &b, &c);
  43. 			--a; --b;
  44. 			g[a].push_back(make_pair(b, c));
  45. 			g[b].push_back(make_pair(a, c));
  46.  
  47. 		}
  48.  
  49. 		int p = dfs(c, -1, INT_MAX, g, mem);
  50. 		printf("%d\n", p);
  51.  
  52. 	}
  53.  
  54. 	return 0;
  55.  
  56. }
  57.