Submission #656301

#	Time	Username	Problem	Language	Result	Execution time	Memory
656301		Dec0Dedd	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2097 ms	262144 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;

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

ll ans=INF, dx[N], dy[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 u : par[v]) {
         G2[v].push_back(u);
      }

      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]) {
      assert(u != v);
      G2[v].push_back(u);
      gen(u);
   }
}

void dfs(int v, ll mx, ll my) {
   mx=min(mx, dx[v]), my=min(my, dy[v]);
   ans=min(ans, mx+my);
   for (auto u : G2[v]) {
      assert(u != v);
      dfs(u, mx, my); 
   }
}

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]=INF;
   dijk(x, dx, false), dijk(y, dy, false);
   dfs(t, INF, INF);

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

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