Submission #1255773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255773		amanthaband	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	125 ms	17016 KiB

commuter_pass

/////scc

/////1.make a dfs and find ending and starting node
/////2.reverse graph
/////3.again dfs


///end.
#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) ((int)(x).size())
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define rrep(i,a,b) for(int i = a; i >= b; --i)

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

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

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

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

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

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

      bool join(int x, int 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;
      }
};

int distt = 0;
set<pii> dijskra(int v, int t, vvi &adj, int 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 (int cur = t; p[cur] != -1; cur = p[cur]) {
            int a = cur, b = p[cur];
            if (a> b) swap(a,b);
            pass.insert({a, b});
      }
      return pass;
}

int digi2(int v, vvi &adj, int src,set<pii> pass,int 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);

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

      vvi adj(n+1);
      for (int i = 0; i < m; i++) {
            int 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);

      
      int 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