#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int NMAX = 1e5 + 1;
vector <vector <pll> > g(NMAX);
ll d[NMAX][4];
vector <vector <int> > p(NMAX);
void Dijkstra(int n, int s, int ind){
d[s][ind] = 0;
priority_queue <pll> q;
q.push({0, s});
vector <bool> used(n + 1);
while(!q.empty()){
int v = q.top().s;
q.pop();
if(used[v]) continue;
used[v] = true;
for(auto x : g[v]){
int to = x.f;
ll l = x.s;
if(d[to][ind] > d[v][ind] + l){
d[to][ind] = d[v][ind] + l;
q.push({-d[to][ind], to});
if(!ind){
p[to].clear();
p[to].pb(v);
}
}
else{
if(d[to][ind] == d[v][ind] + l){
if(!ind) p[to].pb(v);
}
}
}
}
}
vector <vector <int> > G(NMAX);
stack <int> st, st1;
vector <bool> used(NMAX, false);
void dfs(int v){
used[v] = true;
for(int to : G[v]){
if(used[to]) continue;
dfs(to);
}
st.push(v);
st1.push(v);
}
int main(){
int n, m; cin >> n >> m;
int s, t; cin >> s >> t;
int x, y; cin >> x >> y;
for(int i = 1; i <= m; i++){
int u, v;
ll c;
cin >> u >> v >> c;
g[u].pb({v, c});
g[v].pb({u, c});
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < 4; j++) d[i][j] = 1e18;
}
Dijkstra(n, s, 0);
Dijkstra(n, t, 1);
Dijkstra(n, x, 2);
Dijkstra(n, y, 3);
for(int i = 1; i <= n; i++){
for(int to : p[i]) G[to].pb(i);
}
dfs(s);
ll ans[n + 1];
for(int i = 1; i <= n; i++){
ans[i] = 1e18;
}
ll res = d[x][3];
while(!st.empty()){
int v = st.top();
st.pop();
if(d[t][0] != d[v][0] + d[v][1]) continue;
ans[v] = min(d[v][2], ans[v]);
res = min(res, ans[v] + d[v][3]);
for(int to : G[v]){
ans[to] = min(ans[to], ans[v]);
}
}
for(int i = 1; i <= n; i++){
ans[i] = 1e18;
}
while(!st1.empty()){
int v = st1.top();
st1.pop();
if(d[t][0] != d[v][0] + d[v][1]) continue;
ans[v] = min(d[v][3], ans[v]);
res = min(res, ans[v] + d[v][2]);
for(int to : G[v]){
ans[to] = min(ans[to], ans[v]);
}
}
cout << res;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
483 ms |
26704 KB |
Output is correct |
2 |
Correct |
496 ms |
27576 KB |
Output is correct |
3 |
Correct |
478 ms |
30464 KB |
Output is correct |
4 |
Correct |
500 ms |
26964 KB |
Output is correct |
5 |
Correct |
464 ms |
27936 KB |
Output is correct |
6 |
Correct |
506 ms |
26544 KB |
Output is correct |
7 |
Correct |
490 ms |
27980 KB |
Output is correct |
8 |
Correct |
475 ms |
28108 KB |
Output is correct |
9 |
Correct |
529 ms |
26808 KB |
Output is correct |
10 |
Correct |
429 ms |
26524 KB |
Output is correct |
11 |
Correct |
233 ms |
25156 KB |
Output is correct |
12 |
Correct |
502 ms |
27716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
493 ms |
28392 KB |
Output is correct |
2 |
Correct |
523 ms |
28724 KB |
Output is correct |
3 |
Correct |
500 ms |
28724 KB |
Output is correct |
4 |
Correct |
531 ms |
32176 KB |
Output is correct |
5 |
Correct |
524 ms |
32176 KB |
Output is correct |
6 |
Correct |
506 ms |
33820 KB |
Output is correct |
7 |
Correct |
506 ms |
35264 KB |
Output is correct |
8 |
Correct |
486 ms |
32256 KB |
Output is correct |
9 |
Correct |
501 ms |
32204 KB |
Output is correct |
10 |
Correct |
507 ms |
32272 KB |
Output is correct |
11 |
Correct |
240 ms |
27452 KB |
Output is correct |
12 |
Correct |
483 ms |
33928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
8672 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
5 ms |
7380 KB |
Output is correct |
4 |
Correct |
50 ms |
10764 KB |
Output is correct |
5 |
Correct |
22 ms |
9044 KB |
Output is correct |
6 |
Correct |
6 ms |
7452 KB |
Output is correct |
7 |
Correct |
6 ms |
7508 KB |
Output is correct |
8 |
Correct |
7 ms |
7636 KB |
Output is correct |
9 |
Correct |
5 ms |
7508 KB |
Output is correct |
10 |
Correct |
21 ms |
9060 KB |
Output is correct |
11 |
Correct |
4 ms |
7380 KB |
Output is correct |
12 |
Correct |
4 ms |
7380 KB |
Output is correct |
13 |
Correct |
4 ms |
7380 KB |
Output is correct |
14 |
Correct |
5 ms |
7380 KB |
Output is correct |
15 |
Correct |
5 ms |
7372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
483 ms |
26704 KB |
Output is correct |
2 |
Correct |
496 ms |
27576 KB |
Output is correct |
3 |
Correct |
478 ms |
30464 KB |
Output is correct |
4 |
Correct |
500 ms |
26964 KB |
Output is correct |
5 |
Correct |
464 ms |
27936 KB |
Output is correct |
6 |
Correct |
506 ms |
26544 KB |
Output is correct |
7 |
Correct |
490 ms |
27980 KB |
Output is correct |
8 |
Correct |
475 ms |
28108 KB |
Output is correct |
9 |
Correct |
529 ms |
26808 KB |
Output is correct |
10 |
Correct |
429 ms |
26524 KB |
Output is correct |
11 |
Correct |
233 ms |
25156 KB |
Output is correct |
12 |
Correct |
502 ms |
27716 KB |
Output is correct |
13 |
Correct |
493 ms |
28392 KB |
Output is correct |
14 |
Correct |
523 ms |
28724 KB |
Output is correct |
15 |
Correct |
500 ms |
28724 KB |
Output is correct |
16 |
Correct |
531 ms |
32176 KB |
Output is correct |
17 |
Correct |
524 ms |
32176 KB |
Output is correct |
18 |
Correct |
506 ms |
33820 KB |
Output is correct |
19 |
Correct |
506 ms |
35264 KB |
Output is correct |
20 |
Correct |
486 ms |
32256 KB |
Output is correct |
21 |
Correct |
501 ms |
32204 KB |
Output is correct |
22 |
Correct |
507 ms |
32272 KB |
Output is correct |
23 |
Correct |
240 ms |
27452 KB |
Output is correct |
24 |
Correct |
483 ms |
33928 KB |
Output is correct |
25 |
Correct |
29 ms |
8672 KB |
Output is correct |
26 |
Correct |
4 ms |
7380 KB |
Output is correct |
27 |
Correct |
5 ms |
7380 KB |
Output is correct |
28 |
Correct |
50 ms |
10764 KB |
Output is correct |
29 |
Correct |
22 ms |
9044 KB |
Output is correct |
30 |
Correct |
6 ms |
7452 KB |
Output is correct |
31 |
Correct |
6 ms |
7508 KB |
Output is correct |
32 |
Correct |
7 ms |
7636 KB |
Output is correct |
33 |
Correct |
5 ms |
7508 KB |
Output is correct |
34 |
Correct |
21 ms |
9060 KB |
Output is correct |
35 |
Correct |
4 ms |
7380 KB |
Output is correct |
36 |
Correct |
4 ms |
7380 KB |
Output is correct |
37 |
Correct |
4 ms |
7380 KB |
Output is correct |
38 |
Correct |
5 ms |
7380 KB |
Output is correct |
39 |
Correct |
5 ms |
7372 KB |
Output is correct |
40 |
Correct |
428 ms |
30524 KB |
Output is correct |
41 |
Correct |
522 ms |
30796 KB |
Output is correct |
42 |
Correct |
517 ms |
30792 KB |
Output is correct |
43 |
Correct |
249 ms |
26964 KB |
Output is correct |
44 |
Correct |
234 ms |
27004 KB |
Output is correct |
45 |
Correct |
464 ms |
31580 KB |
Output is correct |
46 |
Correct |
462 ms |
31248 KB |
Output is correct |
47 |
Correct |
463 ms |
31104 KB |
Output is correct |
48 |
Correct |
253 ms |
24840 KB |
Output is correct |
49 |
Correct |
391 ms |
30124 KB |
Output is correct |
50 |
Correct |
458 ms |
31280 KB |
Output is correct |
51 |
Correct |
430 ms |
31428 KB |
Output is correct |