fork(2) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
1 6
1 9
https://ideone.com/2C02bU
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!