Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 31st, 2020 88 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e4 + 7, M = 1e5 + 7;
  5. vector<pair<int, int>> graph[N];
  6. int dsu[N], sz[N], n, m, s, t, answer = INT_MAX;
  7. set<int> act;
  8. tuple<int, int, int> arr[M];
  9. vector<int> comp[N];
  10.  
  11. int get(int v) {
  12.   if (dsu[v] == v) {
  13.     return v;
  14.   }
  15.   return dsu[v] = get(dsu[v]);
  16. }
  17.  
  18. void merge(int a, int b) {
  19.   a = get(a);
  20.   b = get(b);
  21.   if (a == b) {
  22.     return;
  23.   }
  24.   if (sz[a] < sz[b]) {
  25.     swap(a, b);
  26.   }
  27.   sz[a] += sz[b];
  28.   dsu[b] = a;
  29.   for (auto i : comp[b]) {
  30.     comp[a].push_back(i);
  31.   }
  32. }
  33.  
  34. int main() {
  35.   ios::sync_with_stdio(0);
  36.   cin.tie(0); cout.tie(0);
  37.  
  38.   cin >> n >> m;
  39.   for (int i = 0; i < m; ++i) {
  40.     int a, b, c;
  41.     cin >> a >> b >> c;
  42.     a--; b--;
  43.     graph[a].emplace_back(b, c);
  44.     graph[b].emplace_back(a, c);
  45.     arr[i] = { c, a , b };
  46.   }
  47.   cin >> s >> t;
  48.   s--; t--;
  49.   sort(arr, arr + m);
  50.   iota(dsu, dsu + n, 0);
  51.   fill(sz, sz + n, 1);
  52.   for (int i = 0; i < n; ++i) {
  53.     comp[i].push_back(i);
  54.   }
  55.   for (auto i : graph[s]) {
  56.     if (get(i.first) == get(t)) {
  57.       act.insert(i.second);
  58.       answer = min(answer, i.second);
  59.     }
  60.   }
  61.   for (int i = 0; i < m; ++i) {
  62.     int a, b, c;
  63.     tie(c, a, b) = arr[i];
  64.     if (get(s) == get(t) || (!act.empty() && c > *act.begin())) {
  65.       break;
  66.     }
  67.     if (get(a) == get(b)) {
  68.       continue;
  69.     }
  70.     if (get(a) != get(s)) {
  71.       swap(a, b);
  72.     }
  73.     if (get(a) == get(s) && get(b) == get(t)) {
  74.       answer = min(answer, c + *act.begin());
  75.       break;
  76.     }
  77.     if (get(a) == get(s)) {
  78.       for (auto i : comp[get(b)]) {
  79.         for (auto j : graph[i]) {
  80.           if (get(j.first) == get(t)) {
  81.             act.insert(j.second);
  82.           }
  83.         }
  84.       }
  85.       merge(a, b);
  86.       if (!act.empty()) {
  87.         answer = min(answer, c + *act.begin());
  88.       }
  89.       continue;
  90.     }
  91.     if (get(a) != get(t)) {
  92.       swap(a, b);
  93.     }
  94.     if (get(a) == get(t)) {
  95.       for (auto i : comp[get(b)]) {
  96.         for (auto j : graph[i]) {
  97.           if (get(j.first) == get(s)) {
  98.             act.insert(j.second);
  99.           }
  100.         }
  101.       }
  102.       merge(a, b);
  103.       if (!act.empty()) {
  104.         answer = min(answer, c + *act.begin());
  105.       }
  106.       continue;
  107.     }
  108.     merge(a, b);
  109.   }
  110.   cout << answer << "\n";
  111.  
  112.   return 0;
  113. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top