#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define inf LLONG_MAX/(ll)2
//nodes, edges, pass start, pass end, person start, person end
ll n, m, s, t, u, v;
vector<vector<pll>> adj;
//path.first -> dag from s to t, path.second -> dag from t to s
vector<vector<ll>> path[2];
//u dist, v dist
vector<ll> dist[2];
//dp[0][i] -> min cost of u going to node along path start -> i
//dp[1][i] -> min cost of v going to node along path i -> end
vector<ll> dp[2];
vector<ll> currDist; vector<vector<ll>> currPath;
vector<ll> getDist(ll src){
priority_queue<pll, vector<pll>, greater<pll>> trav;
vector<ll> dst(n); fill(dst.begin(), dst.end(), inf);
trav.push({0, src}); dst[src] = 0;
while (!trav.empty()){
pll curr = trav.top(); trav.pop();
if (dst[curr.second] != curr.first) continue;
for (pll elem : adj[curr.second]){
ll d = curr.first+elem.first;
if (d < dst[elem.second]){
dst[elem.second] = d;
trav.push({d, elem.second});
}
}
}
return dst;
}
vector<vector<ll>> getPath(ll src){
priority_queue<pll, vector<pll>, greater<pll>> trav; vector<vector<ll>> par(n);
vector<ll> dst(n); fill(dst.begin(), dst.end(), inf);
trav.push({0, src}); dst[src] = 0;
while (!trav.empty()){
pll curr = trav.top(); trav.pop();
if (dst[curr.second] != curr.first) continue;
for (pll elem : adj[curr.second]){
ll d = curr.first+elem.first;
if (d < dst[elem.second]){
dst[elem.second] = d;
par[elem.second].clear(); par[elem.second].push_back(curr.second);
trav.push({d, elem.second});
}
else if (d == dst[elem.second])
par[elem.second].push_back(curr.second);
}
}
return par;
}
//which path -> 0 for backtrack from end, 1 for bactrack from start
//which dist -> 0 for dist from u, 1 for dist from v
ll dfs(ll node, ll whichPath, ll whichDist){
if (dp[whichDist][node] != inf) return dp[whichDist][node];
ll lowest = dist[whichDist][node];
for (ll elem : path[whichPath][node])
lowest = min(lowest, dfs(elem, whichPath, whichDist));
dp[whichDist][node] = lowest;
return lowest;
}
void solve(){
ll ans = dist[0][v];
fill(dp[0].begin(), dp[0].end(), inf); fill(dp[1].begin(), dp[1].end(), inf);
dfs(s, 0, 0);
dfs(t, 1, 1);
for (int i = 0; i < n; i++) ans = min(ans, dp[0][i]+dp[1][i]);
//swap u and v
fill(dp[0].begin(), dp[0].end(), inf); fill(dp[1].begin(), dp[1].end(), inf);
dfs(s, 0, 1);
dfs(t, 1, 0);
for (int i = 0; i < n; i++) ans = min(ans, dp[0][i]+dp[1][i]);
cout<<ans;
}
int main(){
cin >> n >> m >> s >> t >> u >> v; s--, t--, u--, v--;
adj.resize(n); dp[0].resize(n); dp[1].resize(n);
for (int i = 0; i < m; i++){
ll a, b, w; cin >> a >> b >> w; a--, b--;
adj[a].push_back({w, b});
adj[b].push_back({w, a});
}
path[0] = getPath(t);
path[1] = getPath(s);
dist[0] = getDist(u);
dist[1] = getDist(v);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
487 ms |
30680 KB |
Output is correct |
2 |
Correct |
487 ms |
29620 KB |
Output is correct |
3 |
Correct |
522 ms |
37360 KB |
Output is correct |
4 |
Correct |
487 ms |
33932 KB |
Output is correct |
5 |
Correct |
491 ms |
32192 KB |
Output is correct |
6 |
Correct |
495 ms |
33512 KB |
Output is correct |
7 |
Correct |
514 ms |
32060 KB |
Output is correct |
8 |
Correct |
510 ms |
32036 KB |
Output is correct |
9 |
Correct |
493 ms |
32688 KB |
Output is correct |
10 |
Correct |
450 ms |
32804 KB |
Output is correct |
11 |
Correct |
232 ms |
26932 KB |
Output is correct |
12 |
Correct |
505 ms |
32572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
521 ms |
31804 KB |
Output is correct |
2 |
Correct |
528 ms |
32036 KB |
Output is correct |
3 |
Correct |
513 ms |
31484 KB |
Output is correct |
4 |
Correct |
534 ms |
32072 KB |
Output is correct |
5 |
Correct |
514 ms |
32336 KB |
Output is correct |
6 |
Correct |
513 ms |
33924 KB |
Output is correct |
7 |
Correct |
550 ms |
34688 KB |
Output is correct |
8 |
Correct |
507 ms |
31872 KB |
Output is correct |
9 |
Correct |
519 ms |
32368 KB |
Output is correct |
10 |
Correct |
531 ms |
31644 KB |
Output is correct |
11 |
Correct |
231 ms |
27476 KB |
Output is correct |
12 |
Correct |
513 ms |
34196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
2252 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
43 ms |
4080 KB |
Output is correct |
5 |
Correct |
21 ms |
1944 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
460 KB |
Output is correct |
8 |
Correct |
5 ms |
556 KB |
Output is correct |
9 |
Correct |
3 ms |
460 KB |
Output is correct |
10 |
Correct |
21 ms |
1988 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
2 ms |
300 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
487 ms |
30680 KB |
Output is correct |
2 |
Correct |
487 ms |
29620 KB |
Output is correct |
3 |
Correct |
522 ms |
37360 KB |
Output is correct |
4 |
Correct |
487 ms |
33932 KB |
Output is correct |
5 |
Correct |
491 ms |
32192 KB |
Output is correct |
6 |
Correct |
495 ms |
33512 KB |
Output is correct |
7 |
Correct |
514 ms |
32060 KB |
Output is correct |
8 |
Correct |
510 ms |
32036 KB |
Output is correct |
9 |
Correct |
493 ms |
32688 KB |
Output is correct |
10 |
Correct |
450 ms |
32804 KB |
Output is correct |
11 |
Correct |
232 ms |
26932 KB |
Output is correct |
12 |
Correct |
505 ms |
32572 KB |
Output is correct |
13 |
Correct |
521 ms |
31804 KB |
Output is correct |
14 |
Correct |
528 ms |
32036 KB |
Output is correct |
15 |
Correct |
513 ms |
31484 KB |
Output is correct |
16 |
Correct |
534 ms |
32072 KB |
Output is correct |
17 |
Correct |
514 ms |
32336 KB |
Output is correct |
18 |
Correct |
513 ms |
33924 KB |
Output is correct |
19 |
Correct |
550 ms |
34688 KB |
Output is correct |
20 |
Correct |
507 ms |
31872 KB |
Output is correct |
21 |
Correct |
519 ms |
32368 KB |
Output is correct |
22 |
Correct |
531 ms |
31644 KB |
Output is correct |
23 |
Correct |
231 ms |
27476 KB |
Output is correct |
24 |
Correct |
513 ms |
34196 KB |
Output is correct |
25 |
Correct |
23 ms |
2252 KB |
Output is correct |
26 |
Correct |
2 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
332 KB |
Output is correct |
28 |
Correct |
43 ms |
4080 KB |
Output is correct |
29 |
Correct |
21 ms |
1944 KB |
Output is correct |
30 |
Correct |
3 ms |
332 KB |
Output is correct |
31 |
Correct |
3 ms |
460 KB |
Output is correct |
32 |
Correct |
5 ms |
556 KB |
Output is correct |
33 |
Correct |
3 ms |
460 KB |
Output is correct |
34 |
Correct |
21 ms |
1988 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
2 ms |
300 KB |
Output is correct |
37 |
Correct |
2 ms |
332 KB |
Output is correct |
38 |
Correct |
2 ms |
332 KB |
Output is correct |
39 |
Correct |
2 ms |
332 KB |
Output is correct |
40 |
Correct |
468 ms |
33764 KB |
Output is correct |
41 |
Correct |
496 ms |
32580 KB |
Output is correct |
42 |
Correct |
507 ms |
32724 KB |
Output is correct |
43 |
Correct |
255 ms |
27604 KB |
Output is correct |
44 |
Correct |
249 ms |
27572 KB |
Output is correct |
45 |
Correct |
520 ms |
31984 KB |
Output is correct |
46 |
Correct |
519 ms |
32396 KB |
Output is correct |
47 |
Correct |
502 ms |
34044 KB |
Output is correct |
48 |
Correct |
266 ms |
24544 KB |
Output is correct |
49 |
Correct |
490 ms |
35136 KB |
Output is correct |
50 |
Correct |
523 ms |
32604 KB |
Output is correct |
51 |
Correct |
543 ms |
32536 KB |
Output is correct |