Submission #959290

#	Time	Username	Problem	Language	Result	Execution time	Memory
959290		stefanneagu	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	492 ms	25624 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e5 + 1;

vector<vector<pair<int, int>>> adj;

int n;

int pz[nmax], pt[nmax];

vector<int> calc(int a) {
  set<pair<int, int>> s;
  s.insert({0, a});
  vector<int> v(n + 1, 1e18);
  v[a] = 0;
  while(!s.empty()) {
    auto curr = s.begin();
    int sum = (*curr).first, i = (*curr).second;
    s.erase(*curr);
    if(v[i] < sum) {
      continue;
    }
    for(auto it : adj[i]) {
      if(v[it.first] > it.second + sum) {
        v[it.first] = it.second + sum;
        s.insert({it.second + sum, it.first});
      }
    }
  }
  return v;
}

int32_t main() {
  int m;
  cin >> n >> m;
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  adj.resize(n + 1);
  for(int i = 1; i <= m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }
  vector<int> x = calc(A);
  vector<int> y = calc(B);
  vector<int> z = calc(C);
  vector<int> t = calc(D);
  vector<pair<int, int>> vp;
  for(int i = 1; i <= n; i++) {
    if(x[i] + y[i] == x[B]) {
      vp.push_back({x[i], i});

    }
  }
  sort(vp.begin(), vp.end());
  int ans = z[D];
  for(auto i1 : vp) {
    int i = i1.second;
    pz[i] = z[i];
    pt[i] = t[i];
    for(auto it : adj[i]) {
      if(x[it.first] + it.second == x[i]) {
        pz[i] = min(pz[i], pz[it.first]);
        pt[i] = min(pt[i], pt[it.first]);
      }
    }
    ans = min(ans, pz[i] + t[i]);
    ans = min(ans, pt[i] + z[i]);
  }
  cout << ans;
}

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