Source code for submission s714

fr.cpp

  1. #include <algorithm>
  2. #include <cmath>
  3. #include<cstdio>
  4. #include <cstring>
  5. #include <iomanip>
  6. #include <iostream>
  7. #include <list>
  8. #include <map>
  9. #include <queue>
  10. #include <set>
  11. #include <stack>
  12. #include <string>
  13. #include <vector>
  14.  
  15. using namespace std;
  16.  
  17. #define REP(i,n) for ( int i = 0; i < (n); i++)
  18. #define FOR(i,a,b) for ( int i = (a); i <= (b); i++ )
  19. #define FORD(i,a,b) for ( int i = (a); i>= (b); i-- )
  20. #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl;
  21.  
  22. int ** costs;
  23. int ** sib;
  24. int sibCnt[1024];
  25. int visited[1024];
  26. int central;
  27. int n1,n2,cost,nodeCnt;
  28.  
  29. int dfs(int node, int prev) {
  30. if (sibCnt[node] == 1) return costs[prev][node];
  31. int sum = 0;
  32. REP(i,sibCnt[node]) if ( sib[node][i] != prev ) sum += dfs(sib[node][i],node);
  33. return min(sum, costs[prev][node]);
  34. }
  35.  
  36. int solve() {
  37. int sum = 0;
  38. REP(i,sibCnt[central]) sum += dfs(sib[central][i],central);
  39. return sum;
  40. }
  41.  
  42. int main() {
  43. costs = new int * [1024];
  44. sib = new int * [1024];
  45. REP(i,1024) {
  46. costs[i] = new int [1024];
  47. sib[i] = new int [1024];
  48. }
  49. while (scanf("%d%d",&nodeCnt,&central) == 2) {
  50. REP(i,1024) sibCnt[i] = 0;
  51. REP(i,nodeCnt-1) {
  52. scanf("%d%d%d",&n1,&n2,&cost);
  53. sib[n1][sibCnt[n1]++] = n2;
  54. sib[n2][sibCnt[n2]++] = n1;
  55. costs[n1][n2] = costs[n2][n1] = cost;
  56. }
  57. cout << solve() << endl;
  58. }
  59. return 0;
  60. }
  61.