#include <bits/stdc++.h>
using namespace std;
#define task ""
#define fi first
#define se second
#define MASK(i) (1 << (i))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(mask, i) ((mask) >> (i) & 1)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};
const long long INF = 1e18;
const int MAX = 100100;
int n, m;
int S, T;
int U, V;
long long dpU[MAX];
long long dpV[MAX];
long long d[4][MAX];
vector<pair<int, int>> adj[MAX];
void dijkstra(int t, int s) {
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
for (int i = 1; i <= n; ++i) d[t][i] = INF;
pq.push({0, s});
d[t][s] = 0;
while (pq.size()) {
long long dist = pq.top().fi;
int u = pq.top().se;
pq.pop();
if (dist != d[t][u]) continue;
for (pair<int, int> &x: adj[u]) {
int v = x.fi, w = x.se;
if (minimize(d[t][v], dist + w))
pq.push({d[t][v], v});
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".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;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
dijkstra(0, S); dijkstra(1, T);
dijkstra(2, U); dijkstra(3, V);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
for (int i = 1; i <= n; ++i) {
if (d[0][i] + d[1][i] == d[0][T])
pq.push({d[0][i], i});
}
for (int i = 1; i <= n; ++i) {
dpU[i] = dpV[i] = INF;
}
while (pq.size()) {
int i = pq.top().se;
pq.pop();
minimize(dpU[i], d[2][i]);
minimize(dpV[i], d[3][i]);
for (pair<int, int> &x: adj[i]) {
int j = x.fi, w = x.se;
if (d[0][i] + w + d[1][j] == d[0][T]) {
minimize(dpU[j], dpU[i]);
minimize(dpV[j], dpV[i]);
}
}
}
long long ans = d[2][V];
for (int i = 1; i <= n; ++i) {
if (d[0][i] + d[1][i] == d[0][T]) {
minimize(ans, dpU[i] + d[3][i]);
minimize(ans, dpV[i] + d[2][i]);
}
}
cout << ans;
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:56:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:57:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
248 ms |
15140 KB |
Output is correct |
2 |
Correct |
266 ms |
14724 KB |
Output is correct |
3 |
Correct |
269 ms |
20472 KB |
Output is correct |
4 |
Correct |
258 ms |
18952 KB |
Output is correct |
5 |
Correct |
253 ms |
18800 KB |
Output is correct |
6 |
Correct |
270 ms |
19076 KB |
Output is correct |
7 |
Correct |
272 ms |
19016 KB |
Output is correct |
8 |
Correct |
288 ms |
18804 KB |
Output is correct |
9 |
Correct |
264 ms |
18192 KB |
Output is correct |
10 |
Correct |
230 ms |
18160 KB |
Output is correct |
11 |
Correct |
102 ms |
13192 KB |
Output is correct |
12 |
Correct |
255 ms |
18112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
253 ms |
14592 KB |
Output is correct |
2 |
Correct |
300 ms |
14652 KB |
Output is correct |
3 |
Correct |
272 ms |
14512 KB |
Output is correct |
4 |
Correct |
262 ms |
14720 KB |
Output is correct |
5 |
Correct |
285 ms |
15332 KB |
Output is correct |
6 |
Correct |
251 ms |
15544 KB |
Output is correct |
7 |
Correct |
300 ms |
15148 KB |
Output is correct |
8 |
Correct |
250 ms |
14660 KB |
Output is correct |
9 |
Correct |
287 ms |
15160 KB |
Output is correct |
10 |
Correct |
244 ms |
14576 KB |
Output is correct |
11 |
Correct |
98 ms |
11584 KB |
Output is correct |
12 |
Correct |
266 ms |
15656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
14 ms |
4820 KB |
Output is correct |
5 |
Correct |
10 ms |
3756 KB |
Output is correct |
6 |
Correct |
3 ms |
2772 KB |
Output is correct |
7 |
Correct |
3 ms |
2772 KB |
Output is correct |
8 |
Correct |
3 ms |
2900 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
8 ms |
3668 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
3 ms |
2688 KB |
Output is correct |
14 |
Correct |
2 ms |
2772 KB |
Output is correct |
15 |
Correct |
2 ms |
2724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
248 ms |
15140 KB |
Output is correct |
2 |
Correct |
266 ms |
14724 KB |
Output is correct |
3 |
Correct |
269 ms |
20472 KB |
Output is correct |
4 |
Correct |
258 ms |
18952 KB |
Output is correct |
5 |
Correct |
253 ms |
18800 KB |
Output is correct |
6 |
Correct |
270 ms |
19076 KB |
Output is correct |
7 |
Correct |
272 ms |
19016 KB |
Output is correct |
8 |
Correct |
288 ms |
18804 KB |
Output is correct |
9 |
Correct |
264 ms |
18192 KB |
Output is correct |
10 |
Correct |
230 ms |
18160 KB |
Output is correct |
11 |
Correct |
102 ms |
13192 KB |
Output is correct |
12 |
Correct |
255 ms |
18112 KB |
Output is correct |
13 |
Correct |
253 ms |
14592 KB |
Output is correct |
14 |
Correct |
300 ms |
14652 KB |
Output is correct |
15 |
Correct |
272 ms |
14512 KB |
Output is correct |
16 |
Correct |
262 ms |
14720 KB |
Output is correct |
17 |
Correct |
285 ms |
15332 KB |
Output is correct |
18 |
Correct |
251 ms |
15544 KB |
Output is correct |
19 |
Correct |
300 ms |
15148 KB |
Output is correct |
20 |
Correct |
250 ms |
14660 KB |
Output is correct |
21 |
Correct |
287 ms |
15160 KB |
Output is correct |
22 |
Correct |
244 ms |
14576 KB |
Output is correct |
23 |
Correct |
98 ms |
11584 KB |
Output is correct |
24 |
Correct |
266 ms |
15656 KB |
Output is correct |
25 |
Correct |
7 ms |
3412 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
2 ms |
2644 KB |
Output is correct |
28 |
Correct |
14 ms |
4820 KB |
Output is correct |
29 |
Correct |
10 ms |
3756 KB |
Output is correct |
30 |
Correct |
3 ms |
2772 KB |
Output is correct |
31 |
Correct |
3 ms |
2772 KB |
Output is correct |
32 |
Correct |
3 ms |
2900 KB |
Output is correct |
33 |
Correct |
2 ms |
2772 KB |
Output is correct |
34 |
Correct |
8 ms |
3668 KB |
Output is correct |
35 |
Correct |
2 ms |
2644 KB |
Output is correct |
36 |
Correct |
2 ms |
2644 KB |
Output is correct |
37 |
Correct |
3 ms |
2688 KB |
Output is correct |
38 |
Correct |
2 ms |
2772 KB |
Output is correct |
39 |
Correct |
2 ms |
2724 KB |
Output is correct |
40 |
Correct |
292 ms |
19408 KB |
Output is correct |
41 |
Correct |
271 ms |
18144 KB |
Output is correct |
42 |
Correct |
230 ms |
18116 KB |
Output is correct |
43 |
Correct |
125 ms |
14268 KB |
Output is correct |
44 |
Correct |
137 ms |
14300 KB |
Output is correct |
45 |
Correct |
265 ms |
18684 KB |
Output is correct |
46 |
Correct |
261 ms |
18484 KB |
Output is correct |
47 |
Correct |
244 ms |
18920 KB |
Output is correct |
48 |
Correct |
151 ms |
13656 KB |
Output is correct |
49 |
Correct |
212 ms |
19108 KB |
Output is correct |
50 |
Correct |
237 ms |
18504 KB |
Output is correct |
51 |
Correct |
224 ms |
18656 KB |
Output is correct |