#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = (int)(1e6) + 5;
ll D1[N];
ll D2[N];
ll D3[N];
ll D4[N];
vector < pii > g[N];
int n;
void Go(ll D[],int S) {
for (int i = 1;i <= n;++i)
D[i] = 1e18;
D[S] = 0;
priority_queue < pair < ll , int > , vector < pair < ll , int > > , greater < pair < ll , int > > > Q;
Q.push(mp(0,S));
while (!Q.empty()) {
const ll cost = Q.top().fi;
const int node = Q.top().se;
Q.pop();
if (cost != D[node])
continue;
for (auto it : g[node])
if (D[it.fi] > D[node] + it.se)
D[it.fi] = D[node] + it.se,Q.push(mp(D[it.fi],it.fi));
}
}
int was[N];
ll d1[N];
ll d2[N];
int main(void)
{
int m;
int S,T,U,V;
cin>>n>>m>>S>>T>>U>>V;
while (m --) {
int a,b,c;
cin>>a>>b>>c;
g[a].pb(mp(b,c));
g[b].pb(mp(a,c));
}
Go(D1,S);
Go(D2,T);
Go(D3,U);
Go(D4,V);
vi points;
const ll dist = D1[T];
for (int i = 1;i <= n;++i)
if (D1[i] + D2[i] == dist)
points.pb(i);
ll ans = D3[V];
sort(all(points),[&](int x,int y) {
return D1[x] < D1[y];
});
for (auto it : points) {
d1[it] = D3[it];
d2[it] = D4[it];
for (auto edge : g[it]) {
if (D1[edge.fi] + edge.se + D2[it] == dist)
smin(d1[it],d1[edge.fi]),smin(d2[it],d2[edge.fi]);
}
smin(ans,d1[it] + D4[it]);
smin(ans,d2[it] + D3[it]);
}
cout << ans << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
566 ms |
36408 KB |
Output is correct |
2 |
Correct |
573 ms |
36408 KB |
Output is correct |
3 |
Correct |
572 ms |
36636 KB |
Output is correct |
4 |
Correct |
549 ms |
36636 KB |
Output is correct |
5 |
Correct |
547 ms |
36636 KB |
Output is correct |
6 |
Correct |
629 ms |
36952 KB |
Output is correct |
7 |
Correct |
585 ms |
36952 KB |
Output is correct |
8 |
Correct |
544 ms |
36952 KB |
Output is correct |
9 |
Correct |
629 ms |
36952 KB |
Output is correct |
10 |
Correct |
517 ms |
36952 KB |
Output is correct |
11 |
Correct |
233 ms |
36952 KB |
Output is correct |
12 |
Correct |
575 ms |
36952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
581 ms |
36952 KB |
Output is correct |
2 |
Correct |
621 ms |
36952 KB |
Output is correct |
3 |
Correct |
692 ms |
36952 KB |
Output is correct |
4 |
Correct |
599 ms |
36952 KB |
Output is correct |
5 |
Correct |
765 ms |
36952 KB |
Output is correct |
6 |
Correct |
702 ms |
36952 KB |
Output is correct |
7 |
Correct |
839 ms |
36952 KB |
Output is correct |
8 |
Correct |
643 ms |
36952 KB |
Output is correct |
9 |
Correct |
600 ms |
36952 KB |
Output is correct |
10 |
Correct |
612 ms |
36952 KB |
Output is correct |
11 |
Correct |
273 ms |
36952 KB |
Output is correct |
12 |
Correct |
569 ms |
36952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
36952 KB |
Output is correct |
2 |
Correct |
27 ms |
36952 KB |
Output is correct |
3 |
Correct |
21 ms |
36952 KB |
Output is correct |
4 |
Correct |
72 ms |
36952 KB |
Output is correct |
5 |
Correct |
44 ms |
36952 KB |
Output is correct |
6 |
Correct |
23 ms |
36952 KB |
Output is correct |
7 |
Correct |
24 ms |
36952 KB |
Output is correct |
8 |
Correct |
26 ms |
36952 KB |
Output is correct |
9 |
Correct |
24 ms |
36952 KB |
Output is correct |
10 |
Correct |
45 ms |
36952 KB |
Output is correct |
11 |
Correct |
22 ms |
36952 KB |
Output is correct |
12 |
Correct |
22 ms |
36952 KB |
Output is correct |
13 |
Correct |
23 ms |
36952 KB |
Output is correct |
14 |
Correct |
22 ms |
36952 KB |
Output is correct |
15 |
Correct |
22 ms |
36952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
566 ms |
36408 KB |
Output is correct |
2 |
Correct |
573 ms |
36408 KB |
Output is correct |
3 |
Correct |
572 ms |
36636 KB |
Output is correct |
4 |
Correct |
549 ms |
36636 KB |
Output is correct |
5 |
Correct |
547 ms |
36636 KB |
Output is correct |
6 |
Correct |
629 ms |
36952 KB |
Output is correct |
7 |
Correct |
585 ms |
36952 KB |
Output is correct |
8 |
Correct |
544 ms |
36952 KB |
Output is correct |
9 |
Correct |
629 ms |
36952 KB |
Output is correct |
10 |
Correct |
517 ms |
36952 KB |
Output is correct |
11 |
Correct |
233 ms |
36952 KB |
Output is correct |
12 |
Correct |
575 ms |
36952 KB |
Output is correct |
13 |
Correct |
581 ms |
36952 KB |
Output is correct |
14 |
Correct |
621 ms |
36952 KB |
Output is correct |
15 |
Correct |
692 ms |
36952 KB |
Output is correct |
16 |
Correct |
599 ms |
36952 KB |
Output is correct |
17 |
Correct |
765 ms |
36952 KB |
Output is correct |
18 |
Correct |
702 ms |
36952 KB |
Output is correct |
19 |
Correct |
839 ms |
36952 KB |
Output is correct |
20 |
Correct |
643 ms |
36952 KB |
Output is correct |
21 |
Correct |
600 ms |
36952 KB |
Output is correct |
22 |
Correct |
612 ms |
36952 KB |
Output is correct |
23 |
Correct |
273 ms |
36952 KB |
Output is correct |
24 |
Correct |
569 ms |
36952 KB |
Output is correct |
25 |
Correct |
51 ms |
36952 KB |
Output is correct |
26 |
Correct |
27 ms |
36952 KB |
Output is correct |
27 |
Correct |
21 ms |
36952 KB |
Output is correct |
28 |
Correct |
72 ms |
36952 KB |
Output is correct |
29 |
Correct |
44 ms |
36952 KB |
Output is correct |
30 |
Correct |
23 ms |
36952 KB |
Output is correct |
31 |
Correct |
24 ms |
36952 KB |
Output is correct |
32 |
Correct |
26 ms |
36952 KB |
Output is correct |
33 |
Correct |
24 ms |
36952 KB |
Output is correct |
34 |
Correct |
45 ms |
36952 KB |
Output is correct |
35 |
Correct |
22 ms |
36952 KB |
Output is correct |
36 |
Correct |
22 ms |
36952 KB |
Output is correct |
37 |
Correct |
23 ms |
36952 KB |
Output is correct |
38 |
Correct |
22 ms |
36952 KB |
Output is correct |
39 |
Correct |
22 ms |
36952 KB |
Output is correct |
40 |
Correct |
575 ms |
36952 KB |
Output is correct |
41 |
Correct |
568 ms |
36952 KB |
Output is correct |
42 |
Correct |
574 ms |
36952 KB |
Output is correct |
43 |
Correct |
305 ms |
36952 KB |
Output is correct |
44 |
Correct |
264 ms |
36952 KB |
Output is correct |
45 |
Correct |
547 ms |
36952 KB |
Output is correct |
46 |
Correct |
541 ms |
36952 KB |
Output is correct |
47 |
Correct |
571 ms |
40460 KB |
Output is correct |
48 |
Correct |
295 ms |
40460 KB |
Output is correct |
49 |
Correct |
539 ms |
45924 KB |
Output is correct |
50 |
Correct |
552 ms |
48780 KB |
Output is correct |
51 |
Correct |
527 ms |
52180 KB |
Output is correct |