Submission #757083

#	Time	Username	Problem	Language	Result	Execution time	Memory
757083		gun_gan	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	606 ms	20320 KiB

commuter_pass

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

const int MX = 1e5 + 5;

int N, M, S, T, U, V;
ll d[5][MX], dd[MX];
vector<pair<int,int>> g[MX];

void work(int s, int t) {
      for(int i = 1; i <= N; i++) d[t][i] = 1e18;

      priority_queue<pair<ll, ll>> pq;
      pq.push({0, s});
      d[t][s] = 0;
      while(!pq.empty()) {    
            auto [c, v] = pq.top(); pq.pop();
            c = -c;
            if(d[t][v] < c) continue;
            for(auto [u, w] : g[v]) {
                  if(d[t][u] > c + w) {
                        d[t][u] = c + w;
                        pq.push({-d[t][u], u});
                  }
            }
      }
}

int main() {
      ios_base::sync_with_stdio(0); cin.tie(0);

      cin >> N >> M >> S >> T >> U >> V;

      for(int i = 0; i < M; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            g[u].push_back({v, w});
            g[v].push_back({u, w});
      }

      ll ans = 1e18;
      for(int it = 0; it < 2; it++) {
            work(S, 0);
            work(T, 1);
            work(U, 2);
            work(V, 3);

            // solve
            priority_queue<pair<ll, ll>> pq;

            for(int i = 1; i <= N; i++) {
                  if(d[0][i] + d[1][i] == d[0][T]) {
                        dd[i] = d[2][i];
                        pq.push({-dd[i], i}); 
                  } else {
                        dd[i] = 1e18;
                  }
            }

            while(!pq.empty()) {
                  auto [c, v] = pq.top(); pq.pop();
                  c = -c;
                  if(dd[v] < c) continue;
                  for(auto [u, w] : g[v]) {
                        if(d[0][v] + w + d[1][u] == d[0][T] && dd[u] > c) { // in shortest path
                              dd[u] = c;
                              pq.push({-dd[u], u});
                        }
                  }
            }

            for(int i = 1; i <= N; i++) {
                  ans = min(ans, dd[i] + d[3][i]);
            }
            ans = min(ans, d[2][V]);

            swap(U, V);
      }

      cout << ans << '\n';
      
}

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