Submission #656302

#	Time	Username	Problem	Language	Result	Execution time	Memory
656302		Dec0Dedd	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	2093 ms	262148 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<ll, int>

const int N = 1e5+1;
const ll INF = 1e18;

bool vis[N];

vector<pii> G[N];
vector<int> G2[N], par[N];
int n, m, ind[N];

ll ans=INF, dx[N], dy[N], mx[N], my[N];

void dijk(int s, ll *d, bool bl) {
   for (int i=1; i<=n; ++i) d[i]=INF;
   d[s]=0;

   priority_queue<pii, vector<pii>, greater<pii>> pq;
   pq.push({0, s});

   while (!pq.empty()) {
      ll x=pq.top().first, v=pq.top().second; pq.pop();
      if (x > d[v]) continue;

      for (auto z : G[v]) {
         ll w=z.first, u=z.second;
         if (d[u] > d[v]+w) {
            d[u]=d[v]+w;
            pq.push({d[u], u});
            if (bl) par[u].clear(), par[u].push_back(v);
         } else if (d[u] == d[v]+w && bl) par[u].push_back(v);
      }
   }
}

void gen(int v) {
   for (auto u : par[v]) {
      G2[v].push_back(u);
      gen(u);
   }
}

void bfs() {
   queue<int> q;
   for (int i=1; i<=n; ++i) {
      if (ind[i] == 0) q.push(i); 
   }

   while (!q.empty()) {
      int v=q.front(); q.pop();
      mx[v]=min(mx[v], dx[v]), my[v]=min(my[v], dy[v]);
      ans=min({ans, dx[v]+my[v], mx[v]+dy[v]});

      for (auto u : G2[v]) {
         --ind[u];
         mx[u]=min(mx[u], mx[v]), my[u]=min(my[u], my[v]);
         if (ind[u] == 0) q.push(u); 
      }
   }
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);
   cin>>n>>m;

   int s, t; cin>>s>>t;
   int x, y; cin>>x>>y;

   ll d[n+1]={};
   for (int i=1; i<=m; ++i) {
      int a, b, c; cin>>a>>b>>c;
      G[a].push_back({c, b});
      G[b].push_back({c, a});
   } dijk(s, d, true);
   gen(t);

   for (int i=1; i<=n; ++i) par[i].clear();
   for (int i=1; i<=n; ++i) dx[i]=dy[i]=mx[i]=my[i]=INF;
   dijk(x, dx, false), dijk(y, dy, false);
   memset(vis, false, sizeof(vis));

   for (int i=1; i<=n; ++i) {
      for (auto u : G2[i]) ++ind[u];
   }
   bfs();

   ans=min(ans, dx[y]);
   cout<<ans<<"\n";
}

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