Submission #1255774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255774		amanthaband	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	96 ms	17008 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((long long)(x).size())
#define rep(i,a,b) for(long long i = a; i < b; ++i)
#define rrep(i,a,b) for(long long i = a; i >= b; --i)

using ll = long long;
using pii = pair<ll,ll>;
using vi = vector<ll>;
using vvi = vector<vector<pair<ll,ll>>>;
const ll INF = 1e18;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
struct DSU {
      vi p, sz, mn;

      void init(ll n) {
            p.resize(n);
            sz.assign(n, 1);
            mn.resize(n);
            iota(all(p), 0);
            iota(all(mn), 0);
      }

      ll find(ll x) {
            return x == p[x] ? x : p[x] = find(p[x]);
      }

      bool same(ll x, ll y) {
            return find(x) == find(y);
      }

      ll size(ll x) {
            return sz[find(x)];
      }

      ll get_min(ll x) {
            return mn[find(x)];
      }

      bool join(ll x, ll y) {
            x = find(x);
            y = find(y);
            if (x == y) return false;
            if (sz[x] < sz[y]) swap(x, y);
            p[y] = x;
            sz[x] += sz[y];
            mn[x] = min(mn[x], mn[y]);
            return true;
      }
};

ll distt = 0;
set<pii> dijskra(ll v, ll t, vvi &adj, ll src) {
      vi p(v+1, -1);
      vi dist(v+1, INF);
      minpq<pii> pq;
      dist[src] = 0;
      pq.push({0, src});

      while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            for (auto [nxt, wt] : adj[u]) {
                  if (dist[nxt] > dist[u] + wt) {
                        dist[nxt] = dist[u] + wt;
                        p[nxt] = u;
                        pq.push({dist[nxt], nxt});
                  }
            }
      }
      distt = abs(dist[src] - dist[t]);
      set<pii> pass;
      for (ll cur = t; cur != -1; cur = p[cur]) {
            ll a = cur, b = p[cur];
            if (a> b )swap(a,b);
            pass.insert({a, b});
      }
      return pass;
}

ll digi2(ll v, vvi &adj, ll src, set<pii> pass, ll end) {

      for (auto [a, b] : pass) {
            for (auto &pr : adj[a]) if (pr.first == b) pr.second = 0;
            for (auto &pr : adj[b]) if (pr.first == a) pr.second = 0;
      }

      vi dist(v+1, INF);
      minpq<pii> pq;
      dist[src] = 0;
      pq.push({0, src});

      while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            for (auto [nxt, wt] : adj[u]) {
                  if (dist[nxt] > dist[u] + wt) {
                        dist[nxt] = dist[u] + wt;
                        pq.push({dist[nxt], nxt});
                  }
            }
      }
      distt = dist[end];
      return distt;
}

int main() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);

      ll n, m; cin >> n >> m;
      ll s, t; cin >> s >> t;
      ll u, v; cin >> u >> v;

      vvi adj(n+1);
      for (ll i = 0; i < m; i++) {
            ll a, b, c; cin >> a >> b >> c;
            adj[a].push_back({b, c});
            adj[b].push_back({a, c});
      }

      set<pii> commuter_pass = dijskra(n, t, adj, s);

      ll res = digi2(n, adj, u, commuter_pass, v);
      cout << res << endl;
      return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45