Submission #656303

#	Time	Username	Problem	Language	Result	Execution time	Memory
656303		Dec0Dedd	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	317 ms	24768 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];
int n, m, ind[N];

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

void dijk(int s, ll *d) {
   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});
         }
      }
   }
}

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 ds[n+1]={}, dt[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, ds), dijk(t, dt);

   ll k=ds[t];
   for (int i=1; i<=n; ++i) {
      for (auto z : G[i]) {
         if (ds[i]+dt[z.second]+z.first == k) G2[i].push_back(z.second);
         if (ds[z.second]+dt[i]+z.first == k) G2[z.second].push_back(i);
      }
   }

   for (int i=1; i<=n; ++i) dx[i]=dy[i]=mx[i]=my[i]=INF;
   dijk(x, dx), dijk(y, dy);
   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: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45