Submission #1325394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325394		riafhasan2010	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	203 ms	15172 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);
  ll mnU = inf, mnV = inf;
  for(int i = 1; i <= n; i++){
    if(distS[i] + distT[i] == distS[t]){
      mnU = min(mnU, distU[i]);
      mnV = min(mnV, distV[i]);
    }
  }
  cout << min(distU[v], mnU + mnV) << "\n";
}

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