#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 |
1 |
Correct |
410 ms |
23912 KB |
Output is correct |
2 |
Correct |
445 ms |
27380 KB |
Output is correct |
3 |
Correct |
570 ms |
30876 KB |
Output is correct |
4 |
Correct |
385 ms |
35064 KB |
Output is correct |
5 |
Correct |
496 ms |
38548 KB |
Output is correct |
6 |
Correct |
342 ms |
42656 KB |
Output is correct |
7 |
Correct |
540 ms |
45744 KB |
Output is correct |
8 |
Correct |
476 ms |
49312 KB |
Output is correct |
9 |
Correct |
424 ms |
53396 KB |
Output is correct |
10 |
Correct |
384 ms |
57840 KB |
Output is correct |
11 |
Correct |
299 ms |
57840 KB |
Output is correct |
12 |
Correct |
435 ms |
64160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
487 ms |
68248 KB |
Output is correct |
2 |
Correct |
491 ms |
71504 KB |
Output is correct |
3 |
Correct |
479 ms |
75060 KB |
Output is correct |
4 |
Correct |
486 ms |
78664 KB |
Output is correct |
5 |
Correct |
487 ms |
81960 KB |
Output is correct |
6 |
Correct |
558 ms |
85628 KB |
Output is correct |
7 |
Correct |
552 ms |
89232 KB |
Output is correct |
8 |
Correct |
487 ms |
92716 KB |
Output is correct |
9 |
Correct |
503 ms |
96132 KB |
Output is correct |
10 |
Correct |
502 ms |
99732 KB |
Output is correct |
11 |
Correct |
247 ms |
99732 KB |
Output is correct |
12 |
Correct |
557 ms |
105372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
105372 KB |
Output is correct |
2 |
Correct |
9 ms |
105372 KB |
Output is correct |
3 |
Correct |
9 ms |
105372 KB |
Output is correct |
4 |
Correct |
45 ms |
105372 KB |
Output is correct |
5 |
Correct |
29 ms |
105372 KB |
Output is correct |
6 |
Correct |
10 ms |
105372 KB |
Output is correct |
7 |
Correct |
11 ms |
105372 KB |
Output is correct |
8 |
Correct |
13 ms |
105372 KB |
Output is correct |
9 |
Correct |
11 ms |
105372 KB |
Output is correct |
10 |
Correct |
27 ms |
105372 KB |
Output is correct |
11 |
Correct |
11 ms |
105372 KB |
Output is correct |
12 |
Correct |
9 ms |
105372 KB |
Output is correct |
13 |
Correct |
11 ms |
105372 KB |
Output is correct |
14 |
Correct |
11 ms |
105372 KB |
Output is correct |
15 |
Correct |
10 ms |
105372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
410 ms |
23912 KB |
Output is correct |
2 |
Correct |
445 ms |
27380 KB |
Output is correct |
3 |
Correct |
570 ms |
30876 KB |
Output is correct |
4 |
Correct |
385 ms |
35064 KB |
Output is correct |
5 |
Correct |
496 ms |
38548 KB |
Output is correct |
6 |
Correct |
342 ms |
42656 KB |
Output is correct |
7 |
Correct |
540 ms |
45744 KB |
Output is correct |
8 |
Correct |
476 ms |
49312 KB |
Output is correct |
9 |
Correct |
424 ms |
53396 KB |
Output is correct |
10 |
Correct |
384 ms |
57840 KB |
Output is correct |
11 |
Correct |
299 ms |
57840 KB |
Output is correct |
12 |
Correct |
435 ms |
64160 KB |
Output is correct |
13 |
Correct |
487 ms |
68248 KB |
Output is correct |
14 |
Correct |
491 ms |
71504 KB |
Output is correct |
15 |
Correct |
479 ms |
75060 KB |
Output is correct |
16 |
Correct |
486 ms |
78664 KB |
Output is correct |
17 |
Correct |
487 ms |
81960 KB |
Output is correct |
18 |
Correct |
558 ms |
85628 KB |
Output is correct |
19 |
Correct |
552 ms |
89232 KB |
Output is correct |
20 |
Correct |
487 ms |
92716 KB |
Output is correct |
21 |
Correct |
503 ms |
96132 KB |
Output is correct |
22 |
Correct |
502 ms |
99732 KB |
Output is correct |
23 |
Correct |
247 ms |
99732 KB |
Output is correct |
24 |
Correct |
557 ms |
105372 KB |
Output is correct |
25 |
Correct |
28 ms |
105372 KB |
Output is correct |
26 |
Correct |
9 ms |
105372 KB |
Output is correct |
27 |
Correct |
9 ms |
105372 KB |
Output is correct |
28 |
Correct |
45 ms |
105372 KB |
Output is correct |
29 |
Correct |
29 ms |
105372 KB |
Output is correct |
30 |
Correct |
10 ms |
105372 KB |
Output is correct |
31 |
Correct |
11 ms |
105372 KB |
Output is correct |
32 |
Correct |
13 ms |
105372 KB |
Output is correct |
33 |
Correct |
11 ms |
105372 KB |
Output is correct |
34 |
Correct |
27 ms |
105372 KB |
Output is correct |
35 |
Correct |
11 ms |
105372 KB |
Output is correct |
36 |
Correct |
9 ms |
105372 KB |
Output is correct |
37 |
Correct |
11 ms |
105372 KB |
Output is correct |
38 |
Correct |
11 ms |
105372 KB |
Output is correct |
39 |
Correct |
10 ms |
105372 KB |
Output is correct |
40 |
Correct |
414 ms |
111404 KB |
Output is correct |
41 |
Correct |
431 ms |
116052 KB |
Output is correct |
42 |
Correct |
393 ms |
120224 KB |
Output is correct |
43 |
Correct |
253 ms |
120224 KB |
Output is correct |
44 |
Correct |
255 ms |
120224 KB |
Output is correct |
45 |
Correct |
540 ms |
127776 KB |
Output is correct |
46 |
Correct |
510 ms |
131080 KB |
Output is correct |
47 |
Correct |
524 ms |
135268 KB |
Output is correct |
48 |
Correct |
336 ms |
135268 KB |
Output is correct |
49 |
Correct |
377 ms |
140008 KB |
Output is correct |
50 |
Correct |
580 ms |
143680 KB |
Output is correct |
51 |
Correct |
561 ms |
147048 KB |
Output is correct |