Source code for submission s598

fr.cpp

  1.  
  2.  
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6.  
  7. #include<cmath>
  8. #include<cctype>
  9. #include<climits>
  10. #include<algorithm>
  11. #include<utility>
  12. #include<string>
  13.  
  14. #include<deque>
  15. #include<list>
  16. #include<map>
  17. #include<queue>
  18. #include<set>
  19. #include<stack>
  20. #include<vector>
  21.  
  22.  
  23. using namespace std;
  24.  
  25. #define REP(i,N) for (int i = 0; i < (N); i++)
  26. #define FOR(i,a,b) for (int i = (a); i <= (b); i++)
  27. #define FORI(i,a,b) for (int i = (a); i < (b); i++)
  28. #define FORD(i,a,b) for (int i = (a)-1; i >= (b); i--)
  29. #define DP(arg...) fprintf(stderr, ## arg)
  30.  
  31. typedef long long ll;
  32. typedef long double ld;
  33. typedef pair<int,int> ii;
  34.  
  35. ll H[1111][1111];
  36. ll D[1111];
  37. int seen[1111];
  38. int n, c;
  39. vector<int> graf[1111];
  40.  
  41. ll dfs(int v, int p) {
  42. if (graf[v].size()==1 && v!=c) D[v] = 1000000000000LL;
  43. seen[v] = 1;
  44. REP(i, graf[v].size()) {
  45. int u = graf[v][i];
  46. if (!seen[u]) {
  47. dfs(u, v);
  48. D[v] += min(D[u], H[v][u]);
  49. }
  50. }
  51. return D[v];
  52. }
  53.  
  54. void solve() {
  55. REP(i, n+5) { graf[i].clear(); seen[i] = 0; D[i] = 0; }
  56. REP(i, n+5) REP(j, n+5) H[i][j] = 0;
  57. REP(i, n-1) {
  58. int u, v, h; scanf("%d%d%d", &u, &v, &h);
  59. graf[u].push_back(v);
  60. graf[v].push_back(u);
  61. H[u][v] = h; H[v][u] = h;
  62. }
  63. printf("%lld\n", dfs(c, 0));
  64. }
  65.  
  66. int main() {
  67. while (scanf("%d%d", &n, &c) != EOF) {
  68. solve();
  69. }
  70. return 0;
  71. }
  72.