fork(2) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define out(a) copy(a.begin(),a.end(),ostream_iterator<int>(cout," "))
  5. #define pr pair<int,int>
  6. #define pp(a,b,c) make_pair(make_pair(a,b),c)
  7. const int N = 1e5 + 100;
  8. int t, n, m, low[N], disc[N], _par[N], par[N], vist[N], id;
  9. ll best, l[N], r[N];
  10. int src, des;
  11.  
  12. vector<vector<pair<int, int> > > arr;
  13. vector<pair<pr,int> >edges,bridges;
  14. bool cmp(pair<pr,int>a,pair<pr,int>b) {
  15. if(a.first.first != b.first.first)
  16. return a.first.first < b.first.first;
  17. return a.first.second < b.first.second;
  18. }
  19. void dfs(int x) {
  20. static int tim = 0;
  21. low[x] = disc[x] = ++tim;
  22. for (int i = 0, ln = arr[x].size(); i < ln; ++i) {
  23. int y = arr[x][i].first, z = arr[x][i].second;
  24. if (disc[y] == -1) {
  25. par[y] = x;
  26. dfs(y);
  27. low[x] = min(low[x], low[y]);
  28. if (low[y] > disc[x]) {
  29. pair<pr,int>tmp = pp(min(x,y),max(x,y),z);
  30. bridges.push_back(tmp);
  31. }
  32. } else if (par[x] != y)
  33. low[x] = min(low[x], disc[y]);
  34. }
  35. }
  36. void dfs(int x, ll dist) {
  37. if (dist >= best) {
  38. if (dist == best)
  39. des = min(des, x);
  40. else
  41. des = x;
  42. best = dist;
  43. }
  44. vist[x] = id;
  45. for (int i = 0, ln = arr[x].size(); i < ln; ++i) {
  46. int y = arr[x][i].first, z = arr[x][i].second;
  47. if (vist[y] == id)
  48. continue;
  49. par[y] = x;
  50. dfs(y, dist + (ll) z);
  51. }
  52. }
  53. int find(int x) {
  54. return par[x] == x ? x : par[x] = find(par[x]);
  55. }
  56. void unite(int x, int y) {
  57. int a = find(x), b = find(y);
  58. if (a > b)
  59. swap(a, b);
  60. par[b] = a;
  61. }
  62. int main() {
  63. #ifndef ONLINE_JUDGE
  64. freopen("a.in", "r", stdin);
  65. #endif
  66. scanf("%d", &t);
  67. while (t--) {
  68. scanf("%d %d", &n, &m);
  69. arr.clear();
  70. arr.resize(n + 1);
  71. edges.clear();
  72. bridges.clear();
  73. while (m--) {
  74. int x, y, z;
  75. scanf("%d %d %d", &x, &y, &z);
  76. if (x > y)
  77. swap(x, y);
  78. --x,--y;
  79. arr[x].push_back(make_pair(y, z));
  80. arr[y].push_back(make_pair(x, z));
  81. disc[x] = disc[y] = par[x] = par[y] = -1;
  82. edges.push_back(pp(x, y, z));
  83. }
  84. dfs(0);
  85. sort(bridges.begin(), bridges.end());
  86. for (int i = 0; i <= n; ++i)
  87. par[i] = i;
  88. for (size_t i = 0; i < edges.size(); ++i) {
  89. int x = edges[i].first.first, y = edges[i].first.second;
  90. if (binary_search(bridges.begin(), bridges.end(), pp(x, y, 0), cmp))
  91. continue;
  92. unite(x, y);
  93. }
  94. edges.clear();
  95. arr.clear();
  96. arr.resize(n + 1);
  97. for (size_t i = 0; i < bridges.size(); ++i) {
  98. int x = bridges[i].first.first, y = bridges[i].first.second;
  99. int a = find(x), b = find(y);
  100. arr[a].push_back(make_pair(b, bridges[i].second));
  101. arr[b].push_back(make_pair(a, bridges[i].second));
  102. edges.push_back(pp(a, b, bridges[i].second));
  103. }
  104. sort(edges.begin(), edges.end());
  105. src = find(0);
  106. id++;
  107. best = 0;
  108. dfs(src, 0);
  109. memset(par, -1, sizeof par);
  110. memset(_par, -1, sizeof _par);
  111. src = des;
  112. best = 0;
  113. ++id;
  114. dfs(src, 0);
  115. int x = des;
  116. ll sum = 0;
  117. int ans = -1;
  118. while (par[x] != -1) {
  119. int p = x;
  120. x = par[x];
  121. _par[x] = p;
  122. pair<pr,int>tmp = pp(min(x,p),max(x,p),0);
  123. int pos = lower_bound(edges.begin(), edges.end(), tmp, cmp)
  124. - edges.begin();
  125. sum += edges[pos].second;
  126. l[x] = sum;
  127. }
  128. sum = 0;
  129. while (_par[x] != -1) {
  130. int p = x;
  131. x = _par[x];
  132. pair<pr,int>tmp = pp(min(x,p),max(x,p),0);
  133. int pos = lower_bound(edges.begin(), edges.end(), tmp, cmp)
  134. - edges.begin();
  135. sum += edges[pos].second;
  136. r[x] = sum;
  137. }
  138. sum = LLONG_MAX;
  139. while (x != -1) {
  140. ll diff = max(l[x], r[x]);
  141. if (sum >= diff) {
  142. if (sum == diff)
  143. ans = min(ans, x);
  144. else
  145. ans = x;
  146. sum = diff;
  147. }
  148. x = par[x];
  149. }
  150. printf("%d %lld\n", ans+1, sum);
  151. }
  152. return 0;
  153. }
Success #stdin #stdout 0s 6988KB
stdin
2
7 7
1 2 5
1 7 5
3 2 5
1 3 5
3 4 3
6 4 1
4 5 3
5 5
1 2 2
2 3 3
1 3 9
4 1 9
5 3 7
stdout
1 6
1 9