Submission #851638

#	Time	Username	Problem	Language	Result	Execution time	Memory
851638		nguyennehehe	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	197 ms	18744 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define isz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
 
using ld = long double;
const int inf = 2e18;
 
const int N = 1e5 + 5;
 
int n, m, S, T, U, V;
vector<pair<int, int>> g[N];
 
void sub1() {
  function<vector<int>(int)> dijkstra = [&](int s) {
    vector<int> dist(n + 1, inf);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.emplace(0, s);
    dist[s] = 0;
    while (!pq.empty()) {
        int u, du; tie(du, u) = pq.top();
        pq.pop();
        if (du > dist[u]) {
            continue;
        }
 
        for (pair<int, int> it: g[u]) {
            int v, w; tie(v, w) = it;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    return dist;
  };
  vector<int> distS = dijkstra(S);
  vector<int> distT = dijkstra(T);
  vector<int> distV = dijkstra(V);
  int ans = inf, minPath = distS[T];
  for (int i = 1; i <= n; ++i) {
    if (distS[i] + distT[i] == minPath) {
        ans = min(ans, distV[i]);
    }
  }
  cout << ans << '\n';
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
 
  cin >> n >> m >> S >> T >> U >> V;
  for (int i = 1; i <= m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  if (S == U) {
    sub1();
  }
}

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