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 maxn 100010
#define ll long long
#define pil pair<ll, ll>
#define pli pair<ll, ll>
int N, M;
int s, t, u, v;
const ll inf = 1LL << 61; //feels big enough
ll dists[maxn], distu[maxn], distv[maxn], distt[maxn], dists2[maxn];
bool onpath[maxn]; //starts out as false
bool vis[maxn];
ll smallu[maxn], smallv[maxn]; //store the minimum crossing
//run a triple dijkstra
vector<vector<pil>> adj(maxn);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M >> s >> t >> u >> v;
int a, b;
ll c;
for (int i = 0; i < M; i++) {
cin >> a >> b >> c;
adj[a].push_back(pil(b, c));
adj[b].push_back(pil(a, c));
}
//guaranteed graph is connected
priority_queue<pli, vector<pli>, greater<pli>> pq;
fill(dists, dists+maxn, inf);
fill(distu, distu+maxn, inf);
fill(distv, distv+maxn, inf);
fill(distt, distt+maxn, inf);
dists[s] = 0;
distu[u] = 0;
distv[v] = 0;
distt[t] = 0;
pq.push(pli(0, s));
while (pq.size()) {
pil cur = pq.top(); pq.pop();
int x = cur.second;
ll d = cur.first;
if (d > dists[x]) continue;
for (pil nx : adj[x]) {
if (d + nx.second < dists[nx.first]) {
dists[nx.first] = d + nx.second;
pq.push(pil(dists[nx.first], nx.first));
}
}
}
//now we run it for u and then we will do v
pq.push(pli(0, u));
while (pq.size()) {
pil cur = pq.top(); pq.pop();
int x = cur.second;
ll d = cur.first;
if (d > distu[x]) continue;
for (pil nx : adj[x]) {
if (d + nx.second < distu[nx.first]) {
distu[nx.first] = d + nx.second;
pq.push(pil(distu[nx.first], nx.first));
}
}
}
pq.push(pli(0, v));
while (pq.size()) {
pil cur = pq.top(); pq.pop();
int x = cur.second;
ll d = cur.first;
if (d > distv[x]) continue;
for (pil nx : adj[x]) {
if (d + nx.second < distv[nx.first]) {
distv[nx.first] = d + nx.second;
pq.push(pil(distv[nx.first], nx.first));
}
}
}
ll ans = distu[v]; //maybe nothing is on the path
//now we have to find what is on the path and then we can do the dp thing
//we can do the dp by just doing another dijkstra from s b/c easy
//to calculate what is on the path we might want to dijkstra from t??
onpath[t] = true; // we know that
//run a modified dijkstra from t, only adding things if they are on the path
vis[t] = true;
pq.push(pli(0, t));
while (pq.size()) {
pil cur = pq.top(); pq.pop();
int x= cur.second;
if (x == s) break; //no need to go further
ll d = cur.first;
if (d > distt[x]) continue;
for (pil nx : adj[x]) {
if (dists[nx.first] + nx.second != dists[x]) {
continue; //not on path
}
onpath[nx.first] = true;
if (d + nx.second < distt[nx.first]) {
distt[nx.first] = d + nx.second;
pq.push(pil(distt[nx.first], nx.first));
}
}
}
//now we do the dp stuff
fill(dists2, dists2+maxn, inf);
fill(smallu, smallu+maxn, inf);
fill(smallv, smallv+maxn, inf);
dists2[s] = 0LL;
pq.push(pli(0, s));
while (pq.size()) {
pil cur = pq.top(); pq.pop();
int x = cur.second;
ll d = cur.first;
if (d > dists2[x]) continue;
// cout << "gotten here: " << x << endl;
smallu[x] = min(smallu[x], distu[x]);
smallv[x] = min(smallv[x], distv[x]);
ans = min(ans, smallv[x] + distu[x]);
ans = min(ans, smallu[x] + distv[x]);
//process from parents when we go down
for (pil nx : adj[x]) {
if (!onpath[nx.first]) continue;
if (dists[x] + nx.second == dists[nx.first]) {
smallu[nx.first] = min(smallu[nx.first], smallu[x]);
smallv[nx.first] = min(smallv[nx.first], smallv[x]);
}
if (d + nx.second < dists2[nx.first]) {
dists2[nx.first] = d + nx.second;
pq.push(pil(dists2[nx.first], nx.first));
}
}
}
// for (int i = 1; i <= N; i++) {
// if (onpath[i]) cout << i << " is on the path" << endl;
// }
//cout << "printing dist s stuff" << endl;
// for (int i = 1; i <= N; i++) {
// cout << " " << dists[i] << endl;
// }
//right now i should give <= correct
//have to modify the min calculation stuff (should not be hard though)
// cout << "dist u: " << distu[t] << endl;
// cout << "dist v: " << distv[t] << endl;
// cout << "dist s: " << dists[t] << endl;
// cout << "small u: " << smallu[t] << endl;
// cout << "small v: " << smallv[t] << endl;
cout << ans << endl;
}
# | 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... |