Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #ifndef Local
- #define debug(...) 1337
- #define endl '\n'
- #endif
- using namespace std;
- #define int long long
- typedef long long ll;
- typedef long double ld;
- #define all(x) (x).begin(), (x).end()
- #define sz(x) (int)(x).size()
- template<typename T, typename U>
- bool smin(T &a, U b) {
- if (a > b) {
- a = b;
- return true;
- }
- return false;
- }
- template<typename T, typename U>
- bool smax(T &a, U b) {
- if (a < b) {
- a = b;
- return true;
- }
- return false;
- }
- const int maxn = 1e4 + 100;
- vector <pair<int, int>> g[maxn];
- int a, b;
- const int inf = 1e15;
- struct dsu {
- struct comp {
- int p, a = inf, b = inf;
- vector<int> v;
- } c[maxn];
- int p[maxn];
- dsu() {
- for (int i = 1; i < maxn; ++i)
- p[i] = i, c[i].v = {i};
- }
- int find(int v) {
- return p[v] == v ? v : p[v] = find(p[v]);
- }
- int merge(int v, int u) {
- v = find(v), u = find(u);
- if (v == u)
- return 0;
- if (u == a)
- swap(v, u);
- if (u == b) {
- if (v == a)
- return 2;
- swap(v, u);
- }
- if (v != a && v != b && sz(c[v].v) < sz(c[u].v))
- swap(v, u);
- p[u] = v;
- for (int &i: c[u].v)
- c[v].v.emplace_back(i);
- if (v == a) {
- for (int &i: c[u].v)
- for (auto &[j, w]: g[i])
- smin(c[find(j)].a, w);
- } else if (v == b) {
- for (int &i: c[u].v)
- for (auto &[j, w]: g[i])
- smin(c[find(j)].b, w);
- }
- smin(c[v].a, c[u].a);
- smin(c[v].b, c[u].b);
- c[u].v = {};
- return 1;
- }
- };
- void solve() {
- int n, m;
- cin >> n >> m;
- vector <tuple<int, int, int>> edges;
- int ans = inf;
- for (int i = 0, v, u, w; i < m; ++i) {
- cin >> v >> u >> w;
- g[v].emplace_back(u, w);
- g[u].emplace_back(v, w);
- edges.emplace_back(w, v, u);
- }
- cin >> a >> b;
- sort(all(edges));
- dsu dsu;
- for (int i = 1; i <= n; ++i) {
- int ta = (i == a ? 0 : inf), tb = (i == b ? 0 : inf);
- for (auto& [j, w] : g[i]) {
- if (j == a)
- smin(ta, w);
- if (j == b)
- smin(tb, w);
- }
- dsu.c[i].a = ta, dsu.c[i].b = tb;
- smin(ans, ta + tb);
- }
- for (auto& [w, v, u] : edges) {
- int f = dsu.merge(v, u);
- if (!f)
- continue;
- if (f == 2) {
- smin(ans, 3 * w);
- break;
- }
- for (int i = 1; i < maxn; ++i) {
- if (sz(dsu.c[i].v) && i != a && i != b) {
- smin(ans, w * (1 + (i == a) + (i == b)) + dsu.c[i].a + dsu.c[i].b);
- }
- }
- }
- cout << ans << endl;
- }
- signed main() {
- ios::sync_with_stdio(false), cin.tie(nullptr);
- int tt = 1;
- // cin >> tt;
- while (tt--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement