#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <queue>
#include <set>
using namespace std;
using ll = long long;
#define int ll
#define fore(a, b, c) for(int a=b; a<c; ++a)
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define ii pair<int,int>
#define F first
#define S second
const int MAXN = 1e5+5;
vector<ii> adj[MAXN];
int n, m, s, t, u, v;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
fore(i, 0, m){
int x, y, c;
cin >> x >> y >> c;
adj[x].push_back({y, c});
adj[y].push_back({x, c});
}
auto dijkstra = [&](int r, vi &dis) -> void {
dis[r] = 0;
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, r});
while(sz(pq)){
auto [cost, node] = pq.top();
pq.pop();
if(cost != dis[node]) continue;
for(auto [to, c] : adj[node]){
if(dis[node] + c < dis[to]){
dis[to] = dis[node] + c;
pq.push({dis[to], to});
}
}
}
};
vi du(n+1, 4e18), dv(n+1, 4e18), ds(n+1, 4e18);
dijkstra(u, du);
dijkstra(v, dv);
auto dijkstraDag = [&](int r, vi &dis) -> vector<vi> {
vector<vi> parent(n+1);
dis[r] = 0;
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, r});
while(sz(pq)){
auto [cost, node] = pq.top(); pq.pop();
if(dis[node] != cost) continue;
for(auto [to, w] : adj[node]){
if(cost + w < dis[to]){
parent[to].clear();
parent[to].push_back(node);
dis[to] = cost + w;
pq.push({dis[to], to});
}
else if(cost + w == dis[to]){
parent[to].push_back(node);
}
}
}
return parent;
};
vector<vi> parent = dijkstraDag(s, ds);
vector<bool> sirve(n+1);
vi st;
st.push_back(t);
while(sz(st)){
int cur = st.back();
sirve[cur] = 1;
st.pop_back();
for(auto xx : parent[cur]){
if(sirve[xx]) continue;
st.push_back(xx);
}
}
vector<vi> dag(n+1);
fore(i, 1, n+1){
for(auto xx : parent[i]){
dag[xx].push_back(i);
}
}
int ans = du[v];
vector<int> dp(n+1, -1);
auto f = [&](auto self, int node, int who) -> int {
int &res = dp[node];
if(sirve[node] == 0) return res = 4e18;
if(res > -1){
return res;
}
if(who == u){
res = du[node];
} else {
res = dv[node];
}
for(int to : dag[node]){
res = min(res, self(self, to, who));
}
// cerr << "\n============\n";
// cerr << "result para nodo " << node << ": " << res << endl;
return res;
};
fore(x, 1, n+1){
int res = f(f, x, v) + du[x];
ans = min(ans, res);
}
fill(all(dp), -1);
fore(x, 1, n+1){
int res = f(f, x, u) + dv[x];
ans = min(ans, res);
}
// fore(i, 1, n+1){
// cerr << "para nodo " << i << ": ";
// for(auto xx : parent[i]){
// cerr << xx << ' ';
// }
// cerr << "\n===================\n";
// }
cout << ans;
}
Compilation message
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:50:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
50 | auto [cost, node] = pq.top();
| ^
commuter_pass.cpp:55:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
55 | for(auto [to, c] : adj[node]){
| ^
commuter_pass.cpp: In lambda function:
commuter_pass.cpp:77:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | auto [cost, node] = pq.top(); pq.pop();
| ^
commuter_pass.cpp:81:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | for(auto [to, w] : adj[node]){
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
195 ms |
29388 KB |
Output is correct |
2 |
Correct |
209 ms |
29496 KB |
Output is correct |
3 |
Correct |
236 ms |
31532 KB |
Output is correct |
4 |
Correct |
190 ms |
29968 KB |
Output is correct |
5 |
Correct |
222 ms |
30700 KB |
Output is correct |
6 |
Correct |
254 ms |
29020 KB |
Output is correct |
7 |
Correct |
264 ms |
30224 KB |
Output is correct |
8 |
Correct |
205 ms |
30256 KB |
Output is correct |
9 |
Correct |
255 ms |
29784 KB |
Output is correct |
10 |
Correct |
195 ms |
30024 KB |
Output is correct |
11 |
Correct |
82 ms |
25168 KB |
Output is correct |
12 |
Correct |
206 ms |
30468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
244 ms |
29808 KB |
Output is correct |
2 |
Correct |
217 ms |
29932 KB |
Output is correct |
3 |
Correct |
280 ms |
30276 KB |
Output is correct |
4 |
Correct |
231 ms |
29588 KB |
Output is correct |
5 |
Correct |
246 ms |
29668 KB |
Output is correct |
6 |
Correct |
234 ms |
31596 KB |
Output is correct |
7 |
Correct |
241 ms |
31884 KB |
Output is correct |
8 |
Correct |
267 ms |
29836 KB |
Output is correct |
9 |
Correct |
218 ms |
29944 KB |
Output is correct |
10 |
Correct |
215 ms |
30092 KB |
Output is correct |
11 |
Correct |
104 ms |
25680 KB |
Output is correct |
12 |
Correct |
230 ms |
32068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
4188 KB |
Output is correct |
2 |
Correct |
2 ms |
2648 KB |
Output is correct |
3 |
Correct |
1 ms |
2648 KB |
Output is correct |
4 |
Correct |
11 ms |
5724 KB |
Output is correct |
5 |
Correct |
6 ms |
3932 KB |
Output is correct |
6 |
Correct |
2 ms |
2908 KB |
Output is correct |
7 |
Correct |
2 ms |
2908 KB |
Output is correct |
8 |
Correct |
2 ms |
2908 KB |
Output is correct |
9 |
Correct |
2 ms |
2908 KB |
Output is correct |
10 |
Correct |
6 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
2652 KB |
Output is correct |
12 |
Correct |
1 ms |
2652 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2904 KB |
Output is correct |
15 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
195 ms |
29388 KB |
Output is correct |
2 |
Correct |
209 ms |
29496 KB |
Output is correct |
3 |
Correct |
236 ms |
31532 KB |
Output is correct |
4 |
Correct |
190 ms |
29968 KB |
Output is correct |
5 |
Correct |
222 ms |
30700 KB |
Output is correct |
6 |
Correct |
254 ms |
29020 KB |
Output is correct |
7 |
Correct |
264 ms |
30224 KB |
Output is correct |
8 |
Correct |
205 ms |
30256 KB |
Output is correct |
9 |
Correct |
255 ms |
29784 KB |
Output is correct |
10 |
Correct |
195 ms |
30024 KB |
Output is correct |
11 |
Correct |
82 ms |
25168 KB |
Output is correct |
12 |
Correct |
206 ms |
30468 KB |
Output is correct |
13 |
Correct |
244 ms |
29808 KB |
Output is correct |
14 |
Correct |
217 ms |
29932 KB |
Output is correct |
15 |
Correct |
280 ms |
30276 KB |
Output is correct |
16 |
Correct |
231 ms |
29588 KB |
Output is correct |
17 |
Correct |
246 ms |
29668 KB |
Output is correct |
18 |
Correct |
234 ms |
31596 KB |
Output is correct |
19 |
Correct |
241 ms |
31884 KB |
Output is correct |
20 |
Correct |
267 ms |
29836 KB |
Output is correct |
21 |
Correct |
218 ms |
29944 KB |
Output is correct |
22 |
Correct |
215 ms |
30092 KB |
Output is correct |
23 |
Correct |
104 ms |
25680 KB |
Output is correct |
24 |
Correct |
230 ms |
32068 KB |
Output is correct |
25 |
Correct |
7 ms |
4188 KB |
Output is correct |
26 |
Correct |
2 ms |
2648 KB |
Output is correct |
27 |
Correct |
1 ms |
2648 KB |
Output is correct |
28 |
Correct |
11 ms |
5724 KB |
Output is correct |
29 |
Correct |
6 ms |
3932 KB |
Output is correct |
30 |
Correct |
2 ms |
2908 KB |
Output is correct |
31 |
Correct |
2 ms |
2908 KB |
Output is correct |
32 |
Correct |
2 ms |
2908 KB |
Output is correct |
33 |
Correct |
2 ms |
2908 KB |
Output is correct |
34 |
Correct |
6 ms |
4444 KB |
Output is correct |
35 |
Correct |
1 ms |
2652 KB |
Output is correct |
36 |
Correct |
1 ms |
2652 KB |
Output is correct |
37 |
Correct |
1 ms |
2652 KB |
Output is correct |
38 |
Correct |
1 ms |
2904 KB |
Output is correct |
39 |
Correct |
1 ms |
2652 KB |
Output is correct |
40 |
Correct |
184 ms |
29008 KB |
Output is correct |
41 |
Correct |
209 ms |
29468 KB |
Output is correct |
42 |
Correct |
237 ms |
29620 KB |
Output is correct |
43 |
Correct |
101 ms |
25788 KB |
Output is correct |
44 |
Correct |
103 ms |
25800 KB |
Output is correct |
45 |
Correct |
240 ms |
31456 KB |
Output is correct |
46 |
Correct |
259 ms |
31096 KB |
Output is correct |
47 |
Correct |
254 ms |
31132 KB |
Output is correct |
48 |
Correct |
128 ms |
23912 KB |
Output is correct |
49 |
Correct |
206 ms |
29816 KB |
Output is correct |
50 |
Correct |
277 ms |
31224 KB |
Output is correct |
51 |
Correct |
207 ms |
31872 KB |
Output is correct |