Submission #1325950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325950		riafhasan2010	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	231 ms	15292 KiB

commuter_pass

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

const ll inf = 1e18;
const int N = 1e5 + 1;
vector<vector<pair<int,int>>> g(N);
int n, m, s, t, u, v;

vector<ll> dijkstra(int src) {
  vector<ll> dist(n + 1, inf);
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  pq.push({0, src});
  dist[src] = 0;
  while (!pq.empty()){
    auto [w, a] = pq.top(); pq.pop();
    for(auto [b, c] : g[a]){
      if(dist[b] > w + c){
        dist[b] = w + c;
        pq.push({dist[b], b});
      }
    }
  }
  return dist;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> s >> t >> u >> v;
  for(int i = 1; i <= m; i++){
    int a, b, c; cin >> a >> b >> c;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  vector<ll> distS = dijkstra(s);
  vector<ll> distT = dijkstra(t);
  vector<ll> distU = dijkstra(u);
  vector<ll> distV = dijkstra(v);
  vector<int> order(n);
  for (int i = 0; i < n; i++) order[i] = i + 1;
  sort(order.begin(), order.end(), [&](int a, int b) {
    return distS[a] < distS[b];
  });
  vector<ll> mnU(n + 1, inf), mnV(n + 1, inf);
  mnU[s] = distU[s], mnV[s] = distV[s];
  ll ans = min(distU[v], mnU[s] + mnV[s]);
  for (auto a : order) {
    mnU[a] = min(mnU[a], distU[a]);
    mnV[a] = min(mnV[a], distV[a]);
    for (auto [b, c] : g[a]) {
      if (distS[a] + c + distT[b] == distS[t]) {
        mnU[b] = min(mnU[b], mnU[a]);
        mnV[b] = min(mnV[b], mnV[a]);
      }
    }
    if (distS[a] + distT[a] == distS[t]) {
      ans = min({ans, mnU[a] + mnV[a]});
    }
  }
  cout << ans << "\n";
}

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