#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 n, m, S, T, U, V;
long long dp[5][sz];
long long d[5][sz];
//constants
long long INF;
long long ST;
// ------------- FUNCTIONS ------------- //
void Dijkstra(int s, int k){
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);
}
// ------------- SUBTASK ------------- //
namespace SUB1{
bool ok(){
return (S == U);
}
void solve(){
Dijkstra(V, 3);
long long ans = 1e18;
for(int i=1;i<=n;++i){
if(d[0][i] + d[1][i] == d[0][T]){
ans = min(ans, d[3][i]);
}
}
cout<<ans;
//--------------------
exit(0);
}
}
long long ds2[305][305];
namespace SUB2{ // n <= 300
bool ok(){
return (n <= 300);
}
void solve(){
memset(ds2, 63, sizeof(ds2));
for(int i=1;i<=n;++i){
ds2[i][i] = 0;
for(pll p : gr[i]){
ds2[i][p.first] = p.second;
}
}
// Floyd - Warshall
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
ds2[i][j] = min(ds2[i][j], ds2[i][k] + ds2[k][j]);
}
}
}
long long ans = ds2[U][V];
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(ds2[S][i] + ds2[i][j] + ds2[j][T] == ST){
ans = min(ans, ds2[U][i] + ds2[j][V]);
ans = min(ans, ds2[U][j] + ds2[i][V]);
}
}
}
cout<<ans;
//----------------------
exit(0);
}
}
namespace SUB3{
void solve(){
build_DAG(T);
Dijkstra(U, 3);
Dijkstra(V, 4);
memset(dp, 63, sizeof(dp));
for(int i=1;i<=n;++i){
dp[1][i] = d[3][i]; //U -> i
dp[2][i] = d[4][i]; //V -> i
}
topo(S);
for(int u : tp){
for(int v : dag[u]){
dp[1][v] = min(dp[1][v], dp[1][u]);
dp[2][v] = min(dp[2][v], dp[2][u]);
}
}
long long ans = d[3][V];
for(int i=1;i<=n;++i){
ans = min({ans, dp[1][i] + d[4][i], dp[2][i] + d[3][i]});
}
cout<<ans;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("PATHLIB.inp","r",stdin);
// freopen("PATHLIB.out","w",stdout);
cin >> n >> m;
cin >> S >> T;
cin >> U >> V;
for(int i=1;i<=m;++i){
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));
INF = d[0][0];
Dijkstra(S, 0);
Dijkstra(T, 1);
ST = d[0][T];
if(SUB1::ok()){ //S == U
SUB1::solve();
}
if(SUB2::ok()){ //n <= 300
SUB2::solve();
}
SUB3::solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
22484 KB |
Output is correct |
2 |
Correct |
179 ms |
23964 KB |
Output is correct |
3 |
Correct |
191 ms |
24180 KB |
Output is correct |
4 |
Correct |
201 ms |
25156 KB |
Output is correct |
5 |
Correct |
219 ms |
23924 KB |
Output is correct |
6 |
Correct |
207 ms |
25384 KB |
Output is correct |
7 |
Correct |
161 ms |
23888 KB |
Output is correct |
8 |
Correct |
163 ms |
24052 KB |
Output is correct |
9 |
Correct |
187 ms |
24220 KB |
Output is correct |
10 |
Correct |
127 ms |
23876 KB |
Output is correct |
11 |
Correct |
50 ms |
16988 KB |
Output is correct |
12 |
Correct |
162 ms |
24028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
26652 KB |
Output is correct |
2 |
Correct |
217 ms |
27092 KB |
Output is correct |
3 |
Correct |
216 ms |
26580 KB |
Output is correct |
4 |
Correct |
239 ms |
27076 KB |
Output is correct |
5 |
Correct |
219 ms |
27612 KB |
Output is correct |
6 |
Correct |
211 ms |
30344 KB |
Output is correct |
7 |
Correct |
250 ms |
31040 KB |
Output is correct |
8 |
Correct |
229 ms |
27100 KB |
Output is correct |
9 |
Correct |
243 ms |
27852 KB |
Output is correct |
10 |
Correct |
218 ms |
26732 KB |
Output is correct |
11 |
Correct |
84 ms |
25936 KB |
Output is correct |
12 |
Correct |
236 ms |
30864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
13400 KB |
Output is correct |
2 |
Correct |
30 ms |
11868 KB |
Output is correct |
3 |
Correct |
27 ms |
12092 KB |
Output is correct |
4 |
Correct |
38 ms |
14780 KB |
Output is correct |
5 |
Correct |
31 ms |
13404 KB |
Output is correct |
6 |
Correct |
27 ms |
12120 KB |
Output is correct |
7 |
Correct |
32 ms |
12188 KB |
Output is correct |
8 |
Correct |
33 ms |
12124 KB |
Output is correct |
9 |
Correct |
28 ms |
12124 KB |
Output is correct |
10 |
Correct |
31 ms |
13400 KB |
Output is correct |
11 |
Correct |
29 ms |
11868 KB |
Output is correct |
12 |
Correct |
27 ms |
11864 KB |
Output is correct |
13 |
Correct |
27 ms |
11868 KB |
Output is correct |
14 |
Correct |
27 ms |
12096 KB |
Output is correct |
15 |
Correct |
27 ms |
11868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
22484 KB |
Output is correct |
2 |
Correct |
179 ms |
23964 KB |
Output is correct |
3 |
Correct |
191 ms |
24180 KB |
Output is correct |
4 |
Correct |
201 ms |
25156 KB |
Output is correct |
5 |
Correct |
219 ms |
23924 KB |
Output is correct |
6 |
Correct |
207 ms |
25384 KB |
Output is correct |
7 |
Correct |
161 ms |
23888 KB |
Output is correct |
8 |
Correct |
163 ms |
24052 KB |
Output is correct |
9 |
Correct |
187 ms |
24220 KB |
Output is correct |
10 |
Correct |
127 ms |
23876 KB |
Output is correct |
11 |
Correct |
50 ms |
16988 KB |
Output is correct |
12 |
Correct |
162 ms |
24028 KB |
Output is correct |
13 |
Correct |
275 ms |
26652 KB |
Output is correct |
14 |
Correct |
217 ms |
27092 KB |
Output is correct |
15 |
Correct |
216 ms |
26580 KB |
Output is correct |
16 |
Correct |
239 ms |
27076 KB |
Output is correct |
17 |
Correct |
219 ms |
27612 KB |
Output is correct |
18 |
Correct |
211 ms |
30344 KB |
Output is correct |
19 |
Correct |
250 ms |
31040 KB |
Output is correct |
20 |
Correct |
229 ms |
27100 KB |
Output is correct |
21 |
Correct |
243 ms |
27852 KB |
Output is correct |
22 |
Correct |
218 ms |
26732 KB |
Output is correct |
23 |
Correct |
84 ms |
25936 KB |
Output is correct |
24 |
Correct |
236 ms |
30864 KB |
Output is correct |
25 |
Correct |
32 ms |
13400 KB |
Output is correct |
26 |
Correct |
30 ms |
11868 KB |
Output is correct |
27 |
Correct |
27 ms |
12092 KB |
Output is correct |
28 |
Correct |
38 ms |
14780 KB |
Output is correct |
29 |
Correct |
31 ms |
13404 KB |
Output is correct |
30 |
Correct |
27 ms |
12120 KB |
Output is correct |
31 |
Correct |
32 ms |
12188 KB |
Output is correct |
32 |
Correct |
33 ms |
12124 KB |
Output is correct |
33 |
Correct |
28 ms |
12124 KB |
Output is correct |
34 |
Correct |
31 ms |
13400 KB |
Output is correct |
35 |
Correct |
29 ms |
11868 KB |
Output is correct |
36 |
Correct |
27 ms |
11864 KB |
Output is correct |
37 |
Correct |
27 ms |
11868 KB |
Output is correct |
38 |
Correct |
27 ms |
12096 KB |
Output is correct |
39 |
Correct |
27 ms |
11868 KB |
Output is correct |
40 |
Correct |
205 ms |
24868 KB |
Output is correct |
41 |
Correct |
187 ms |
24376 KB |
Output is correct |
42 |
Correct |
183 ms |
24344 KB |
Output is correct |
43 |
Correct |
87 ms |
26228 KB |
Output is correct |
44 |
Correct |
85 ms |
26176 KB |
Output is correct |
45 |
Correct |
209 ms |
27796 KB |
Output is correct |
46 |
Correct |
231 ms |
27260 KB |
Output is correct |
47 |
Correct |
186 ms |
25248 KB |
Output is correct |
48 |
Correct |
86 ms |
24196 KB |
Output is correct |
49 |
Correct |
167 ms |
24936 KB |
Output is correct |
50 |
Correct |
204 ms |
26320 KB |
Output is correct |
51 |
Correct |
200 ms |
27356 KB |
Output is correct |