#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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
459 ms |
24488 KB |
Output is correct |
2 |
Correct |
453 ms |
24140 KB |
Output is correct |
3 |
Correct |
419 ms |
25412 KB |
Output is correct |
4 |
Correct |
442 ms |
24516 KB |
Output is correct |
5 |
Correct |
389 ms |
24756 KB |
Output is correct |
6 |
Correct |
581 ms |
24604 KB |
Output is correct |
7 |
Correct |
478 ms |
24932 KB |
Output is correct |
8 |
Correct |
437 ms |
24900 KB |
Output is correct |
9 |
Correct |
460 ms |
24148 KB |
Output is correct |
10 |
Correct |
347 ms |
24384 KB |
Output is correct |
11 |
Correct |
158 ms |
16820 KB |
Output is correct |
12 |
Correct |
472 ms |
23780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
504 ms |
24348 KB |
Output is correct |
2 |
Correct |
482 ms |
23860 KB |
Output is correct |
3 |
Correct |
511 ms |
23660 KB |
Output is correct |
4 |
Correct |
495 ms |
23896 KB |
Output is correct |
5 |
Correct |
521 ms |
24032 KB |
Output is correct |
6 |
Correct |
446 ms |
25256 KB |
Output is correct |
7 |
Correct |
473 ms |
24976 KB |
Output is correct |
8 |
Correct |
465 ms |
23952 KB |
Output is correct |
9 |
Correct |
497 ms |
24088 KB |
Output is correct |
10 |
Correct |
506 ms |
23700 KB |
Output is correct |
11 |
Correct |
148 ms |
17604 KB |
Output is correct |
12 |
Correct |
437 ms |
25248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
6476 KB |
Output is correct |
2 |
Correct |
4 ms |
5068 KB |
Output is correct |
3 |
Correct |
4 ms |
5068 KB |
Output is correct |
4 |
Correct |
21 ms |
7852 KB |
Output is correct |
5 |
Correct |
12 ms |
6456 KB |
Output is correct |
6 |
Correct |
4 ms |
5068 KB |
Output is correct |
7 |
Correct |
6 ms |
5196 KB |
Output is correct |
8 |
Correct |
6 ms |
5196 KB |
Output is correct |
9 |
Correct |
4 ms |
5068 KB |
Output is correct |
10 |
Correct |
12 ms |
6388 KB |
Output is correct |
11 |
Correct |
3 ms |
5032 KB |
Output is correct |
12 |
Correct |
4 ms |
5068 KB |
Output is correct |
13 |
Correct |
4 ms |
5068 KB |
Output is correct |
14 |
Correct |
4 ms |
5068 KB |
Output is correct |
15 |
Correct |
4 ms |
5068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
459 ms |
24488 KB |
Output is correct |
2 |
Correct |
453 ms |
24140 KB |
Output is correct |
3 |
Correct |
419 ms |
25412 KB |
Output is correct |
4 |
Correct |
442 ms |
24516 KB |
Output is correct |
5 |
Correct |
389 ms |
24756 KB |
Output is correct |
6 |
Correct |
581 ms |
24604 KB |
Output is correct |
7 |
Correct |
478 ms |
24932 KB |
Output is correct |
8 |
Correct |
437 ms |
24900 KB |
Output is correct |
9 |
Correct |
460 ms |
24148 KB |
Output is correct |
10 |
Correct |
347 ms |
24384 KB |
Output is correct |
11 |
Correct |
158 ms |
16820 KB |
Output is correct |
12 |
Correct |
472 ms |
23780 KB |
Output is correct |
13 |
Correct |
504 ms |
24348 KB |
Output is correct |
14 |
Correct |
482 ms |
23860 KB |
Output is correct |
15 |
Correct |
511 ms |
23660 KB |
Output is correct |
16 |
Correct |
495 ms |
23896 KB |
Output is correct |
17 |
Correct |
521 ms |
24032 KB |
Output is correct |
18 |
Correct |
446 ms |
25256 KB |
Output is correct |
19 |
Correct |
473 ms |
24976 KB |
Output is correct |
20 |
Correct |
465 ms |
23952 KB |
Output is correct |
21 |
Correct |
497 ms |
24088 KB |
Output is correct |
22 |
Correct |
506 ms |
23700 KB |
Output is correct |
23 |
Correct |
148 ms |
17604 KB |
Output is correct |
24 |
Correct |
437 ms |
25248 KB |
Output is correct |
25 |
Correct |
13 ms |
6476 KB |
Output is correct |
26 |
Correct |
4 ms |
5068 KB |
Output is correct |
27 |
Correct |
4 ms |
5068 KB |
Output is correct |
28 |
Correct |
21 ms |
7852 KB |
Output is correct |
29 |
Correct |
12 ms |
6456 KB |
Output is correct |
30 |
Correct |
4 ms |
5068 KB |
Output is correct |
31 |
Correct |
6 ms |
5196 KB |
Output is correct |
32 |
Correct |
6 ms |
5196 KB |
Output is correct |
33 |
Correct |
4 ms |
5068 KB |
Output is correct |
34 |
Correct |
12 ms |
6388 KB |
Output is correct |
35 |
Correct |
3 ms |
5032 KB |
Output is correct |
36 |
Correct |
4 ms |
5068 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
4 ms |
5068 KB |
Output is correct |
39 |
Correct |
4 ms |
5068 KB |
Output is correct |
40 |
Correct |
584 ms |
27520 KB |
Output is correct |
41 |
Correct |
474 ms |
24132 KB |
Output is correct |
42 |
Correct |
506 ms |
24156 KB |
Output is correct |
43 |
Correct |
174 ms |
18372 KB |
Output is correct |
44 |
Correct |
153 ms |
18404 KB |
Output is correct |
45 |
Correct |
502 ms |
25984 KB |
Output is correct |
46 |
Correct |
378 ms |
25856 KB |
Output is correct |
47 |
Correct |
494 ms |
24624 KB |
Output is correct |
48 |
Correct |
148 ms |
17844 KB |
Output is correct |
49 |
Correct |
419 ms |
27192 KB |
Output is correct |
50 |
Correct |
389 ms |
25412 KB |
Output is correct |
51 |
Correct |
373 ms |
26288 KB |
Output is correct |