Source code for submission s557

fr.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17.  
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25. const int INF = 1<<29;
  26.  
  27. typedef long long ll;
  28.  
  29. #define maxN 1005
  30.  
  31. int n,c;
  32. int u,v,w;
  33. vector<int> edges[maxN];
  34. vector<ll> prizes[maxN];
  35. int father[maxN];
  36. ll fatherprize[maxN];
  37. ll sum;
  38.  
  39. ll comp(int u){
  40. 	if(edges[u].size()==1) return fatherprize[u];
  41. 	ll ans = 0;
  42. 	REP(i,edges[u].size()){
  43. 		if(edges[u][i]==father[u]) continue;
  44. 		father[edges[u][i]]=u;
  45. 		fatherprize[edges[u][i]]=prizes[u][i];
  46. 		ans += comp(edges[u][i]);
  47. 	}
  48. 	ans = min(ans,fatherprize[u]);
  49. 	return ans;
  50. }
  51.  
  52. int main() {
  53. 	while(scanf("%d%d",&n,&c)==2){
  54. 		sum = 0;
  55. 		c--;
  56. 		REP(i,n){ edges[i].clear(); prizes[i].clear(); }
  57. 		REP(i,n-1){
  58. 			scanf("%d%d%d",&u,&v,&w);
  59. 			u--; v--;
  60. 			edges[u].push_back(v); edges[v].push_back(u);
  61. 			prizes[u].push_back(w); prizes[v].push_back(w);
  62. 		}
  63.  
  64. 		REP(i,edges[c].size()){
  65. 			father[edges[c][i]]=c;
  66. 			fatherprize[edges[c][i]]=prizes[c][i];
  67. 			sum += comp(edges[c][i]);
  68. 		}
  69. 		printf("%lld\n",sum);
  70. 	}
  71.  
  72. 	return 0;
  73. }
  74.