#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pll pair<long long, long long>
const int sz = 1e5 + 5;
vector<pll> gr[sz];
long long d[5][sz];
long long f[5][sz];
int n, m, S, T, U, V;
//constants
long long ST;
long long UV;
void Dijkstra(int k, int s){
priority_queue<pll> q;
d[k][s] = 0;
q.push({0, s});
while(q.size()){
long long w, u;
tie(w, u) = q.top();
w = -w;
q.pop();
if(w > d[k][u]){
continue;
}
for(pll p : gr[u]){
long long v, c;
tie(v, c) = p;
if(w + c < d[k][v]){
d[k][v] = w + c;
q.push({-d[k][v], v});
}
}
}
}
vector<int> dag[sz];
int vi[sz];
void build_DAG(int v){
vi[v] = 1;
for(pll p : gr[v]){
long long u, c;
tie(u, c) = p;
if(d[0][u] + c + d[1][v] == ST){
dag[u].push_back(v);
if(vi[u] == 0){
build_DAG(u);
}
}
}
}
deque<int> tp;
void topo(int u){
vi[u] = 2;
for(int v : dag[u]){
if(vi[v] != 2){
topo(v);
}
}
tp.push_front(u);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("main.inp","r",stdin);
// freopen("main.out","w",stdout);
cin >> n >> m;
cin >> S >> T;
cin >> U >> V;
while(m--){
int u, v, c;
cin>>u>>v>>c;
gr[u].push_back({v, c});
gr[v].push_back({u, c});
}
memset(d, 63, sizeof(d));
Dijkstra(0, S);
Dijkstra(1, T);
Dijkstra(2, U);
Dijkstra(3, V);
ST = d[0][T];
UV = d[2][V];
build_DAG(T);
topo(S);
for(int i=1;i<=n;++i){
f[0][i] = d[2][i]; // U -> i
f[1][i] = d[3][i]; // V -> i
}
for(int u : tp){
for(int v : dag[u]){
f[0][v] = min(f[0][v], f[0][u]);
f[1][v] = min(f[1][v], f[1][u]);
}
}
long long ans = UV;
for(int i=1;i<=n;++i){
if(d[0][i] + d[1][i] == ST){
ans = min({ans, f[0][i] + d[3][i], f[1][i] + d[2][i]});
}
}
cout<<ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
201 ms |
28256 KB |
Output is correct |
2 |
Correct |
190 ms |
27568 KB |
Output is correct |
3 |
Correct |
208 ms |
34012 KB |
Output is correct |
4 |
Correct |
208 ms |
27956 KB |
Output is correct |
5 |
Correct |
236 ms |
28400 KB |
Output is correct |
6 |
Correct |
214 ms |
28212 KB |
Output is correct |
7 |
Correct |
231 ms |
28852 KB |
Output is correct |
8 |
Correct |
211 ms |
28672 KB |
Output is correct |
9 |
Correct |
197 ms |
27440 KB |
Output is correct |
10 |
Correct |
170 ms |
27852 KB |
Output is correct |
11 |
Correct |
72 ms |
24916 KB |
Output is correct |
12 |
Correct |
197 ms |
27284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
230 ms |
29444 KB |
Output is correct |
2 |
Correct |
251 ms |
29868 KB |
Output is correct |
3 |
Correct |
280 ms |
29172 KB |
Output is correct |
4 |
Correct |
216 ms |
29512 KB |
Output is correct |
5 |
Correct |
220 ms |
30300 KB |
Output is correct |
6 |
Correct |
248 ms |
32808 KB |
Output is correct |
7 |
Correct |
236 ms |
33672 KB |
Output is correct |
8 |
Correct |
222 ms |
29600 KB |
Output is correct |
9 |
Correct |
268 ms |
30152 KB |
Output is correct |
10 |
Correct |
221 ms |
29136 KB |
Output is correct |
11 |
Correct |
82 ms |
27456 KB |
Output is correct |
12 |
Correct |
257 ms |
33168 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
12888 KB |
Output is correct |
2 |
Correct |
2 ms |
11096 KB |
Output is correct |
3 |
Correct |
3 ms |
11100 KB |
Output is correct |
4 |
Correct |
12 ms |
14632 KB |
Output is correct |
5 |
Correct |
7 ms |
12888 KB |
Output is correct |
6 |
Correct |
3 ms |
11100 KB |
Output is correct |
7 |
Correct |
3 ms |
11100 KB |
Output is correct |
8 |
Correct |
3 ms |
11352 KB |
Output is correct |
9 |
Correct |
3 ms |
11100 KB |
Output is correct |
10 |
Correct |
8 ms |
12892 KB |
Output is correct |
11 |
Correct |
2 ms |
11100 KB |
Output is correct |
12 |
Correct |
2 ms |
11100 KB |
Output is correct |
13 |
Correct |
2 ms |
11100 KB |
Output is correct |
14 |
Correct |
2 ms |
11100 KB |
Output is correct |
15 |
Correct |
2 ms |
11100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
201 ms |
28256 KB |
Output is correct |
2 |
Correct |
190 ms |
27568 KB |
Output is correct |
3 |
Correct |
208 ms |
34012 KB |
Output is correct |
4 |
Correct |
208 ms |
27956 KB |
Output is correct |
5 |
Correct |
236 ms |
28400 KB |
Output is correct |
6 |
Correct |
214 ms |
28212 KB |
Output is correct |
7 |
Correct |
231 ms |
28852 KB |
Output is correct |
8 |
Correct |
211 ms |
28672 KB |
Output is correct |
9 |
Correct |
197 ms |
27440 KB |
Output is correct |
10 |
Correct |
170 ms |
27852 KB |
Output is correct |
11 |
Correct |
72 ms |
24916 KB |
Output is correct |
12 |
Correct |
197 ms |
27284 KB |
Output is correct |
13 |
Correct |
230 ms |
29444 KB |
Output is correct |
14 |
Correct |
251 ms |
29868 KB |
Output is correct |
15 |
Correct |
280 ms |
29172 KB |
Output is correct |
16 |
Correct |
216 ms |
29512 KB |
Output is correct |
17 |
Correct |
220 ms |
30300 KB |
Output is correct |
18 |
Correct |
248 ms |
32808 KB |
Output is correct |
19 |
Correct |
236 ms |
33672 KB |
Output is correct |
20 |
Correct |
222 ms |
29600 KB |
Output is correct |
21 |
Correct |
268 ms |
30152 KB |
Output is correct |
22 |
Correct |
221 ms |
29136 KB |
Output is correct |
23 |
Correct |
82 ms |
27456 KB |
Output is correct |
24 |
Correct |
257 ms |
33168 KB |
Output is correct |
25 |
Correct |
8 ms |
12888 KB |
Output is correct |
26 |
Correct |
2 ms |
11096 KB |
Output is correct |
27 |
Correct |
3 ms |
11100 KB |
Output is correct |
28 |
Correct |
12 ms |
14632 KB |
Output is correct |
29 |
Correct |
7 ms |
12888 KB |
Output is correct |
30 |
Correct |
3 ms |
11100 KB |
Output is correct |
31 |
Correct |
3 ms |
11100 KB |
Output is correct |
32 |
Correct |
3 ms |
11352 KB |
Output is correct |
33 |
Correct |
3 ms |
11100 KB |
Output is correct |
34 |
Correct |
8 ms |
12892 KB |
Output is correct |
35 |
Correct |
2 ms |
11100 KB |
Output is correct |
36 |
Correct |
2 ms |
11100 KB |
Output is correct |
37 |
Correct |
2 ms |
11100 KB |
Output is correct |
38 |
Correct |
2 ms |
11100 KB |
Output is correct |
39 |
Correct |
2 ms |
11100 KB |
Output is correct |
40 |
Correct |
200 ms |
27784 KB |
Output is correct |
41 |
Correct |
212 ms |
27208 KB |
Output is correct |
42 |
Correct |
213 ms |
27236 KB |
Output is correct |
43 |
Correct |
78 ms |
27732 KB |
Output is correct |
44 |
Correct |
117 ms |
27612 KB |
Output is correct |
45 |
Correct |
195 ms |
29668 KB |
Output is correct |
46 |
Correct |
238 ms |
29548 KB |
Output is correct |
47 |
Correct |
195 ms |
27900 KB |
Output is correct |
48 |
Correct |
76 ms |
25172 KB |
Output is correct |
49 |
Correct |
154 ms |
27520 KB |
Output is correct |
50 |
Correct |
189 ms |
28996 KB |
Output is correct |
51 |
Correct |
221 ms |
29984 KB |
Output is correct |