#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n;
ll dist[3][100005];
const ll INF = 1000000000000000LL;
vector <pair <int, int>> graf[100005];
void dij(int gde, int root){
for(int i=1; i<=n; i++) dist[gde][i] = INF;
dist[gde][root] = 0;
set <pair <ll, int>> q;
q.insert({0, root});
while(!q.empty()){
int v = q.begin()->second;
q.erase(q.begin());
for(auto c : graf[v]){
if(dist[gde][c.first] > dist[gde][v]+c.second){
q.erase({dist[gde][c.first], c.first});
dist[gde][c.first] = c.second + dist[gde][v];
q.insert({dist[gde][c.first], c.first});
}
}
}
}
ll mn1[100005];
ll mn2[100005];
vector <int> gr[100005];
int ka[200005];
int kb[200005];
ll kc[200005];
int deg[200005];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int m;
cin >> n >> m;
int s1, t1, s2, t2;
cin >> s1 >> t1 >> s2 >> t2;
for(int i=1; i<=m; i++){
int a, b, c;
cin >> a >> b >> c;
graf[a].push_back({b, c});
graf[b].push_back({a, c});
ka[i] = a;
kb[i] = b;
kc[i] = c;
}
dij(1, s1);
dij(2, t1);
for(int i=1; i<=m; i++){
if(dist[1][ka[i]] > dist[1][kb[i]]) swap(ka[i], kb[i]);
if(dist[1][t1] != dist[1][ka[i]] + kc[i] + dist[2][kb[i]]) continue;
gr[kb[i]].push_back(ka[i]);
deg[ka[i]]++;
}
dij(1, s2);
dij(2, t2);
queue <int> q;
for(int i=1; i<=n; i++){
mn1[i] = mn2[i] = INF;
if(!deg[i]) q.push(i);
}
ll res = dist[1][t2];
while(!q.empty()){
int v = q.front();
q.pop();
res = min(res, mn1[v] + dist[2][v]);
res = min(res, mn2[v] + dist[1][v]);
mn1[v] = min(mn1[v], dist[1][v]);
mn2[v] = min(mn2[v], dist[2][v]);
for(auto c : gr[v]){
deg[c]--;
mn1[c] = min(mn1[c], mn1[v]);
mn2[c] = min(mn2[c], mn2[v]);
if(!deg[c]) q.push(c);
}
}
cout << res << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
588 ms |
24572 KB |
Output is correct |
2 |
Correct |
516 ms |
24312 KB |
Output is correct |
3 |
Correct |
502 ms |
25576 KB |
Output is correct |
4 |
Correct |
567 ms |
24768 KB |
Output is correct |
5 |
Correct |
468 ms |
24824 KB |
Output is correct |
6 |
Correct |
600 ms |
24824 KB |
Output is correct |
7 |
Correct |
492 ms |
25080 KB |
Output is correct |
8 |
Correct |
502 ms |
24952 KB |
Output is correct |
9 |
Correct |
509 ms |
24056 KB |
Output is correct |
10 |
Correct |
373 ms |
24440 KB |
Output is correct |
11 |
Correct |
168 ms |
16888 KB |
Output is correct |
12 |
Correct |
591 ms |
23828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
603 ms |
24384 KB |
Output is correct |
2 |
Correct |
570 ms |
24184 KB |
Output is correct |
3 |
Correct |
556 ms |
23928 KB |
Output is correct |
4 |
Correct |
587 ms |
23940 KB |
Output is correct |
5 |
Correct |
603 ms |
24184 KB |
Output is correct |
6 |
Correct |
534 ms |
25340 KB |
Output is correct |
7 |
Correct |
619 ms |
25080 KB |
Output is correct |
8 |
Correct |
609 ms |
23928 KB |
Output is correct |
9 |
Correct |
643 ms |
24056 KB |
Output is correct |
10 |
Correct |
589 ms |
23800 KB |
Output is correct |
11 |
Correct |
243 ms |
17392 KB |
Output is correct |
12 |
Correct |
525 ms |
25336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
6528 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
20 ms |
7808 KB |
Output is correct |
5 |
Correct |
12 ms |
6400 KB |
Output is correct |
6 |
Correct |
5 ms |
5248 KB |
Output is correct |
7 |
Correct |
5 ms |
5248 KB |
Output is correct |
8 |
Correct |
6 ms |
5248 KB |
Output is correct |
9 |
Correct |
6 ms |
5248 KB |
Output is correct |
10 |
Correct |
16 ms |
6452 KB |
Output is correct |
11 |
Correct |
4 ms |
5120 KB |
Output is correct |
12 |
Correct |
5 ms |
5120 KB |
Output is correct |
13 |
Correct |
4 ms |
5120 KB |
Output is correct |
14 |
Correct |
5 ms |
5120 KB |
Output is correct |
15 |
Correct |
4 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
588 ms |
24572 KB |
Output is correct |
2 |
Correct |
516 ms |
24312 KB |
Output is correct |
3 |
Correct |
502 ms |
25576 KB |
Output is correct |
4 |
Correct |
567 ms |
24768 KB |
Output is correct |
5 |
Correct |
468 ms |
24824 KB |
Output is correct |
6 |
Correct |
600 ms |
24824 KB |
Output is correct |
7 |
Correct |
492 ms |
25080 KB |
Output is correct |
8 |
Correct |
502 ms |
24952 KB |
Output is correct |
9 |
Correct |
509 ms |
24056 KB |
Output is correct |
10 |
Correct |
373 ms |
24440 KB |
Output is correct |
11 |
Correct |
168 ms |
16888 KB |
Output is correct |
12 |
Correct |
591 ms |
23828 KB |
Output is correct |
13 |
Correct |
603 ms |
24384 KB |
Output is correct |
14 |
Correct |
570 ms |
24184 KB |
Output is correct |
15 |
Correct |
556 ms |
23928 KB |
Output is correct |
16 |
Correct |
587 ms |
23940 KB |
Output is correct |
17 |
Correct |
603 ms |
24184 KB |
Output is correct |
18 |
Correct |
534 ms |
25340 KB |
Output is correct |
19 |
Correct |
619 ms |
25080 KB |
Output is correct |
20 |
Correct |
609 ms |
23928 KB |
Output is correct |
21 |
Correct |
643 ms |
24056 KB |
Output is correct |
22 |
Correct |
589 ms |
23800 KB |
Output is correct |
23 |
Correct |
243 ms |
17392 KB |
Output is correct |
24 |
Correct |
525 ms |
25336 KB |
Output is correct |
25 |
Correct |
12 ms |
6528 KB |
Output is correct |
26 |
Correct |
4 ms |
5120 KB |
Output is correct |
27 |
Correct |
4 ms |
5120 KB |
Output is correct |
28 |
Correct |
20 ms |
7808 KB |
Output is correct |
29 |
Correct |
12 ms |
6400 KB |
Output is correct |
30 |
Correct |
5 ms |
5248 KB |
Output is correct |
31 |
Correct |
5 ms |
5248 KB |
Output is correct |
32 |
Correct |
6 ms |
5248 KB |
Output is correct |
33 |
Correct |
6 ms |
5248 KB |
Output is correct |
34 |
Correct |
16 ms |
6452 KB |
Output is correct |
35 |
Correct |
4 ms |
5120 KB |
Output is correct |
36 |
Correct |
5 ms |
5120 KB |
Output is correct |
37 |
Correct |
4 ms |
5120 KB |
Output is correct |
38 |
Correct |
5 ms |
5120 KB |
Output is correct |
39 |
Correct |
4 ms |
5120 KB |
Output is correct |
40 |
Correct |
789 ms |
27628 KB |
Output is correct |
41 |
Correct |
707 ms |
24312 KB |
Output is correct |
42 |
Correct |
652 ms |
24184 KB |
Output is correct |
43 |
Correct |
252 ms |
18552 KB |
Output is correct |
44 |
Correct |
233 ms |
18552 KB |
Output is correct |
45 |
Correct |
524 ms |
25976 KB |
Output is correct |
46 |
Correct |
550 ms |
25976 KB |
Output is correct |
47 |
Correct |
740 ms |
24716 KB |
Output is correct |
48 |
Correct |
233 ms |
17912 KB |
Output is correct |
49 |
Correct |
648 ms |
27372 KB |
Output is correct |
50 |
Correct |
531 ms |
25544 KB |
Output is correct |
51 |
Correct |
485 ms |
26036 KB |
Output is correct |