This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
Commuter Pass
https://oj.uz/problem/view/JOI18_commuter_pass
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;
const int N = 1e5;
const LL INF = 1e18;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m; cin >> n >> m;
int s, t, u, v; cin >> s >> t >> u >> v, s--, t--, u--, v--;
static vector<pair<int, int>> g[N];
while (m--) {
int i, j, c; cin >> i >> j >> c, i--, j--;
g[i].push_back({j, c}), g[j].push_back({i, c});
}
auto gen = [&](int s, LL *dt) {
min_pq<pair<LL, int>> q;
fill(dt, dt + n, INF);
q.push({dt[s] = 0, s});
while (!q.empty()) {
auto [d, i] = q.top(); q.pop();
if (d != dt[i]) continue;
for (auto [j, c] : g[i])
if (d + c < dt[j])
q.push({dt[j] = d + c, j});
}
};
static LL ds[N], dt[N];
gen(s, ds), gen(t, dt);
static LL f[N][3];
LL all = ds[t];
for (int i = 0; i < n; i++) f[i][0] = f[i][1] = f[i][2] = INF;
min_pq<tuple<LL, int, int>> q;
q.push({f[u][0] = 0, u, 0});
while (!q.empty()) {
auto [d, i, t] = q.top(); q.pop();
if (d != f[i][t]) continue;
for (auto [j, c] : g[i]) {
if ((t == 0 || t == 1) && ds[i] + dt[j] + c == all && d < f[j][1])
q.push({f[j][1] = d, j, 1});
if (t == 0 && d + c < f[j][0])
q.push({f[j][0] = d + c, j, 0});
if ((t == 1 || t == 2) && d + c < f[j][2])
q.push({f[j][2] = d + c, j, 2});
}
}
LL tmp = min({f[v][0], f[v][1], f[v][2]});
for (int i = 0; i < n; i++) f[i][0] = f[i][1] = f[i][2] = INF;
q.push({f[u][0] = 0, u, 0});
while (!q.empty()) {
auto [d, i, t] = q.top(); q.pop();
if (d != f[i][t]) continue;
for (auto [j, c] : g[i]) {
if ((t == 0 || t == 1) && dt[i] + ds[j] + c == all && d < f[j][1])
q.push({f[j][1] = d, j, 1});
if (t == 0 && d + c < f[j][0])
q.push({f[j][0] = d + c, j, 0});
if ((t == 1 || t == 2) && d + c < f[j][2])
q.push({f[j][2] = d + c, j, 2});
}
}
tmp = min(tmp, min({f[v][0], f[v][1], f[v][2]}));
cout << tmp << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |