#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const long long INF = 1e18;
const int N = 1e5 + 4;
int n, m;
int S, T;
int U, V;
long long d[N][4];
long long dp[N][2];
vector<pair<int, int>> adj[N];
void Dijkstra(int s, int type) {
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[i][type] = INF; pq.push(make_pair(0, s)); d[s][type] = 0;
while (pq.size()) {
long long du = pq.top().fi;
int u = pq.top().se;
pq.pop();
if (du != d[u][type]) continue;
for (pair<int, int> x: adj[u]) {
int v = x.fi, w = x.se;
if (mini(d[v][type], du + w))
pq.push(make_pair(d[v][type], v));
}
}
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
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, w; cin >> u >> v >> w;
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
Dijkstra(S, 0); Dijkstra(T, 1);
Dijkstra(U, 2); Dijkstra(V, 3);
for (int i = 1; i <= n; i++)
dp[i][0] = dp[i][1] = INF;
// calc array dp[_][__]
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[i][0] + d[i][1] == d[T][0])
pq.push(make_pair(d[i][0], i));
}
while (pq.size()) {
long long du = pq.top().fi;
int u = pq.top().se;
pq.pop();
mini(dp[u][0], d[u][2]);
mini(dp[u][1], d[u][3]);
for (pair<int, int> x: adj[u]) {
int v = x.fi, w = x.se;
if (du + w + d[v][1] == d[T][0]) {
mini(dp[v][0], dp[u][0]);
mini(dp[v][1], dp[u][1]);
}
}
}
long long ans = d[V][2];
for (int i = 1; i <= n; i++) {
if (d[i][0] + d[i][1] == d[T][0]) {
mini(ans, dp[i][0] + d[i][3]);
mini(ans, dp[i][1] + d[i][2]);
}
}
cout << ans;
}
Compilation message
commuter_pass.cpp: In function 'void Dijkstra(int, int)':
commuter_pass.cpp:27:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
27 | for (int i = 1; i <= n; i++) d[i][type] = INF; pq.push(make_pair(0, s)); d[s][type] = 0;
| ^~~
commuter_pass.cpp:27:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
27 | for (int i = 1; i <= n; i++) d[i][type] = INF; pq.push(make_pair(0, s)); d[s][type] = 0;
| ^~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
42 | main() {
| ^~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
289 ms |
19060 KB |
Output is correct |
2 |
Correct |
317 ms |
18044 KB |
Output is correct |
3 |
Correct |
344 ms |
20388 KB |
Output is correct |
4 |
Correct |
304 ms |
18916 KB |
Output is correct |
5 |
Correct |
298 ms |
18868 KB |
Output is correct |
6 |
Correct |
286 ms |
19128 KB |
Output is correct |
7 |
Correct |
346 ms |
19056 KB |
Output is correct |
8 |
Correct |
288 ms |
18804 KB |
Output is correct |
9 |
Correct |
280 ms |
18128 KB |
Output is correct |
10 |
Correct |
225 ms |
18172 KB |
Output is correct |
11 |
Correct |
122 ms |
13584 KB |
Output is correct |
12 |
Correct |
323 ms |
18180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
277 ms |
18248 KB |
Output is correct |
2 |
Correct |
308 ms |
18124 KB |
Output is correct |
3 |
Correct |
301 ms |
17996 KB |
Output is correct |
4 |
Correct |
299 ms |
18008 KB |
Output is correct |
5 |
Correct |
333 ms |
18720 KB |
Output is correct |
6 |
Correct |
275 ms |
19192 KB |
Output is correct |
7 |
Correct |
298 ms |
19992 KB |
Output is correct |
8 |
Correct |
308 ms |
18072 KB |
Output is correct |
9 |
Correct |
314 ms |
18596 KB |
Output is correct |
10 |
Correct |
311 ms |
18120 KB |
Output is correct |
11 |
Correct |
146 ms |
13636 KB |
Output is correct |
12 |
Correct |
312 ms |
19332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
3796 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
13 ms |
4824 KB |
Output is correct |
5 |
Correct |
8 ms |
3704 KB |
Output is correct |
6 |
Correct |
3 ms |
2772 KB |
Output is correct |
7 |
Correct |
3 ms |
2820 KB |
Output is correct |
8 |
Correct |
3 ms |
2772 KB |
Output is correct |
9 |
Correct |
3 ms |
2688 KB |
Output is correct |
10 |
Correct |
10 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 |
2 ms |
2688 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
289 ms |
19060 KB |
Output is correct |
2 |
Correct |
317 ms |
18044 KB |
Output is correct |
3 |
Correct |
344 ms |
20388 KB |
Output is correct |
4 |
Correct |
304 ms |
18916 KB |
Output is correct |
5 |
Correct |
298 ms |
18868 KB |
Output is correct |
6 |
Correct |
286 ms |
19128 KB |
Output is correct |
7 |
Correct |
346 ms |
19056 KB |
Output is correct |
8 |
Correct |
288 ms |
18804 KB |
Output is correct |
9 |
Correct |
280 ms |
18128 KB |
Output is correct |
10 |
Correct |
225 ms |
18172 KB |
Output is correct |
11 |
Correct |
122 ms |
13584 KB |
Output is correct |
12 |
Correct |
323 ms |
18180 KB |
Output is correct |
13 |
Correct |
277 ms |
18248 KB |
Output is correct |
14 |
Correct |
308 ms |
18124 KB |
Output is correct |
15 |
Correct |
301 ms |
17996 KB |
Output is correct |
16 |
Correct |
299 ms |
18008 KB |
Output is correct |
17 |
Correct |
333 ms |
18720 KB |
Output is correct |
18 |
Correct |
275 ms |
19192 KB |
Output is correct |
19 |
Correct |
298 ms |
19992 KB |
Output is correct |
20 |
Correct |
308 ms |
18072 KB |
Output is correct |
21 |
Correct |
314 ms |
18596 KB |
Output is correct |
22 |
Correct |
311 ms |
18120 KB |
Output is correct |
23 |
Correct |
146 ms |
13636 KB |
Output is correct |
24 |
Correct |
312 ms |
19332 KB |
Output is correct |
25 |
Correct |
8 ms |
3796 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
2 ms |
2644 KB |
Output is correct |
28 |
Correct |
13 ms |
4824 KB |
Output is correct |
29 |
Correct |
8 ms |
3704 KB |
Output is correct |
30 |
Correct |
3 ms |
2772 KB |
Output is correct |
31 |
Correct |
3 ms |
2820 KB |
Output is correct |
32 |
Correct |
3 ms |
2772 KB |
Output is correct |
33 |
Correct |
3 ms |
2688 KB |
Output is correct |
34 |
Correct |
10 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 |
2 ms |
2688 KB |
Output is correct |
38 |
Correct |
2 ms |
2644 KB |
Output is correct |
39 |
Correct |
2 ms |
2644 KB |
Output is correct |
40 |
Correct |
264 ms |
19584 KB |
Output is correct |
41 |
Correct |
297 ms |
18240 KB |
Output is correct |
42 |
Correct |
271 ms |
18192 KB |
Output is correct |
43 |
Correct |
154 ms |
14764 KB |
Output is correct |
44 |
Correct |
137 ms |
14740 KB |
Output is correct |
45 |
Correct |
256 ms |
20100 KB |
Output is correct |
46 |
Correct |
305 ms |
19896 KB |
Output is correct |
47 |
Correct |
260 ms |
18860 KB |
Output is correct |
48 |
Correct |
177 ms |
14100 KB |
Output is correct |
49 |
Correct |
244 ms |
19164 KB |
Output is correct |
50 |
Correct |
275 ms |
20108 KB |
Output is correct |
51 |
Correct |
265 ms |
20112 KB |
Output is correct |