This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
struct edge {
int u, v, w;
};
int n, ans;
vector<vector<pair<int, int>>> adj(100005);
vector<vector<int>> g(100005), g2(100005);
vector<int> du(100005), dv(100005);
vector<int> deg1(100005, 0), deg2(100005, 0);
vector<edge> edges;
void dijk(int s, vector<int>& di, vector<vector<pair<int, int>>>& G) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
for (int i = 1; i <= n; i++) di[i] = INF;
di[s] = 0;
q.push({di[s], s});
while (!q.empty()) {
auto [d, u] = q.top();
q.pop();
if (di[u] != d) continue;
for (auto& [v, w] : G[u]) {
if (di[u] + w < di[v]) {
di[v] = di[u] + w;
q.push({di[v], v});
}
}
}
}
void dijk2(vector<int>& dp, vector<vector<int>>& G, vector<int>& deg) {
queue<int> q;
vector<int> di(n + 1);
for (int i = 1; i <= n; i++) {
di[i] = du[i];
if (!du[i]) q.push(i);
}
while (!q.empty()) {
int u = q.front();
q.pop();
// cout << u << '\n';
ans = min(ans, di[u] + dv[u]);
for (auto& v : G[u]) {
deg[v]--;
di[v] = min(du[v], di[u]);
if (deg[v] == 0) q.push(v);
}
}
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
while (m--) {
int x, y, w;
cin >> x >> y >> w;
edges.push_back({x, y, w});
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
vector<int> ds(n+1), dt(n+1), dp(n+1), dp2(n+1);
dijk(s, ds, adj); dijk(t, dt, adj); dijk(u, du, adj); dijk(v, dv, adj);
vector<bool> nodes(n+1, 0);
for (int i = 1; i <= n; i++) if (ds[i] + dt[i] == ds[t]) nodes[i] = 1;
for (auto& [x, y, w] : edges) {
if (ds[x] + dt[y] + w == ds[t]) {
g[x].push_back(y);
g2[y].push_back(x);
deg1[y]++, deg2[x]++;
// cout << x << ' ' << y << '\n';
} else if (ds[y] + dt[x] + w == ds[t]) {
g[y].push_back(x);
g2[x].push_back(y);
deg1[x]++, deg2[y]++;
// cout << x << " " << y << '\n';
}
}
ans = du[v];
dijk2(dp, g, deg1); dijk2(dp2, g2, deg2);
cout << ans << '\n';
}
# | 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... |