Submission #833444

#	Time	Username	Problem	Language	Result	Execution time	Memory
833444		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	402 ms	16532 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;
vector<pair<int,int>> g[MX];
ll dist[5][MX];

void work(int src, int id) {
      priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
      pq.push({0, src});
      dist[id][src] = 0;

      while(!pq.empty()) {
            auto [cost, v] = pq.top();
            pq.pop();
            if(cost > dist[id][v]) continue;
            for(auto [u, w] : g[v]) {
                  if(dist[id][u] > dist[id][v] + w) {
                        dist[id][u] = dist[id][v] + w;
                        pq.push({dist[id][u], u});
                  }
            }
      }
}

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

      cin >> N >> M >> S >> T >> U >> V;
      for(int i = 0; i < M; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            g[a].push_back({b, c});
            g[b].push_back({a, c});
      }

      ll ans = 1e18;

      for(int it = 0; it < 2; it++) {
            for(int j = 0; j < 5; j++)
                  for(int i = 0; i < MX; i++)
                        dist[j][i] = 1e18;

            work(S, 0);
            work(T, 1);
            work(U, 2);
            work(V, 3);

            priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
            
            for(int i = 1; i <= N; i++) {
                  if(dist[0][i] + dist[1][i] == dist[0][T]) {
                        dist[4][i] = dist[2][i];
                        pq.push({dist[2][i], i}); 
                  }
            }

            while(!pq.empty()) {
                  auto [cost, v] = pq.top(); pq.pop();
                  if(cost > dist[4][v]) continue;

                  for(auto [u, w] : g[v]) {
                        if(w + dist[0][v] + dist[1][u] == dist[0][T] && dist[4][u] > cost) {
                              dist[4][u] = cost;
                              pq.push({cost, u});
                        }
                  }
            }

            ans = min(ans, dist[2][V]);
            for(int i = 1; i <= N; i++) {
                  if(dist[0][i] + dist[1][i] == dist[0][T]) {
                        ans = min(ans, dist[4][i] + dist[3][i]);
                  }
            }

            swap(U, V);
      }

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

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