#include<bits/stdc++.h>
using namespace std;
ostream& operator<<(ostream &out, string str) {
for(char c : str) out << c;
return out;
}
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
return out << "(" << p.first << ", " << p.second << ")";
}
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
out << "{";
for(auto it = a.begin(); it != a.end(); it = next(it))
out << (it != a.begin() ? ", " : "") << *it;
return out << "}";
}
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
cerr << a << ", ";
dump(x...);
}
#ifdef DEBUG
# define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
# define debug(...) false
#endif
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
template<class T> int size(T && a) { return a.size(); }
using LL = long long;
using PII = pair<int, int>;
vector<vector<PII>> graph;
vector<LL> get_dist(int n, int s) {
vector<LL> dist(n, 1e18);
priority_queue<pair<LL, int>> Q;
auto push = [&](int v, LL d) {
dist[v] = d;
Q.emplace(-dist[v], v);
};
push(s, 0);
while(!Q.empty()) {
int v = Q.top().ND;
Q.pop();
for(PII e : graph[v]) {
if(dist[e.ST] > dist[v] + e.ND)
push(e.ST, dist[v] + e.ND);
}
}
return dist;
}
vector<bool> vis;
vector<vector<int>> directed;
void dfs(int v, vector<LL> &d) {
vis[v] = true;
for(PII e : graph[v]) {
if(d[v] == d[e.ST] + e.ND) {
directed[v].emplace_back(e.ST);
if(not vis[e.ST])
dfs(e.ST, d);
}
}
}
vector<int> get_topologic_order(int n) {
vector<int> ret, deg(n), Q;
REP(i, n) for(int u : directed[i]) deg[u]++;
REP(i, n) if(deg[i] == 0) Q.emplace_back(i);
while(!Q.empty()) {
int v = Q.back();
Q.pop_back();
ret.emplace_back(v);
for(int u : directed[v]) {
if(--deg[u] == 0)
Q.emplace_back(u);
}
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
int s, t, u, v;
cin >> s >> t >> u >> v;
s--, t--, u--, v--;
graph.resize(n);
REP(i, m) {
int a, b, c;
cin >> a >> b >> c;
graph[a - 1].emplace_back(b - 1, c);
graph[b - 1].emplace_back(a - 1, c);
}
auto dist_u = get_dist(n, u);
auto dist_v = get_dist(n, v);
auto dist_s = get_dist(n, s);
auto dist_t = get_dist(n, t);
debug(dist_s, dist_t);
directed.resize(n);
vis.resize(n);
dfs(s, dist_t);
vector<int> ord = get_topologic_order(n);
vector<LL> min_u(n, 1e18), min_v(n, 1e18);
LL ans = 1e18;
for(int i : ord) {
min_u[i] = min(min_u[i], dist_u[i]);
min_v[i] = min(min_v[i], dist_v[i]);
ans = min(ans, dist_u[i] + min_v[i]);
ans = min(ans, min_u[i] + dist_v[i]);
for(int j : directed[i]) {
min_u[j] = min(min_u[j], min_u[i]);
min_v[j] = min(min_v[j], min_v[i]);
}
}
cout << ans << "\n";
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:117:23: warning: statement has no effect [-Wunused-value]
debug(dist_s, dist_t);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
396 ms |
16980 KB |
Output is correct |
2 |
Correct |
380 ms |
17396 KB |
Output is correct |
3 |
Correct |
416 ms |
22368 KB |
Output is correct |
4 |
Correct |
323 ms |
17196 KB |
Output is correct |
5 |
Correct |
341 ms |
17916 KB |
Output is correct |
6 |
Correct |
386 ms |
17020 KB |
Output is correct |
7 |
Correct |
517 ms |
18408 KB |
Output is correct |
8 |
Correct |
405 ms |
18056 KB |
Output is correct |
9 |
Correct |
423 ms |
17136 KB |
Output is correct |
10 |
Correct |
320 ms |
17024 KB |
Output is correct |
11 |
Correct |
131 ms |
17412 KB |
Output is correct |
12 |
Correct |
381 ms |
16984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
389 ms |
18948 KB |
Output is correct |
2 |
Correct |
398 ms |
19344 KB |
Output is correct |
3 |
Correct |
411 ms |
18960 KB |
Output is correct |
4 |
Correct |
408 ms |
19296 KB |
Output is correct |
5 |
Correct |
404 ms |
19776 KB |
Output is correct |
6 |
Correct |
376 ms |
21992 KB |
Output is correct |
7 |
Correct |
460 ms |
22472 KB |
Output is correct |
8 |
Correct |
428 ms |
19332 KB |
Output is correct |
9 |
Correct |
469 ms |
19796 KB |
Output is correct |
10 |
Correct |
424 ms |
18884 KB |
Output is correct |
11 |
Correct |
149 ms |
19280 KB |
Output is correct |
12 |
Correct |
399 ms |
22316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
892 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
19 ms |
2424 KB |
Output is correct |
5 |
Correct |
11 ms |
1400 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
4 ms |
504 KB |
Output is correct |
8 |
Correct |
4 ms |
504 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
11 ms |
1400 KB |
Output is correct |
11 |
Correct |
3 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
376 KB |
Output is correct |
15 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
396 ms |
16980 KB |
Output is correct |
2 |
Correct |
380 ms |
17396 KB |
Output is correct |
3 |
Correct |
416 ms |
22368 KB |
Output is correct |
4 |
Correct |
323 ms |
17196 KB |
Output is correct |
5 |
Correct |
341 ms |
17916 KB |
Output is correct |
6 |
Correct |
386 ms |
17020 KB |
Output is correct |
7 |
Correct |
517 ms |
18408 KB |
Output is correct |
8 |
Correct |
405 ms |
18056 KB |
Output is correct |
9 |
Correct |
423 ms |
17136 KB |
Output is correct |
10 |
Correct |
320 ms |
17024 KB |
Output is correct |
11 |
Correct |
131 ms |
17412 KB |
Output is correct |
12 |
Correct |
381 ms |
16984 KB |
Output is correct |
13 |
Correct |
389 ms |
18948 KB |
Output is correct |
14 |
Correct |
398 ms |
19344 KB |
Output is correct |
15 |
Correct |
411 ms |
18960 KB |
Output is correct |
16 |
Correct |
408 ms |
19296 KB |
Output is correct |
17 |
Correct |
404 ms |
19776 KB |
Output is correct |
18 |
Correct |
376 ms |
21992 KB |
Output is correct |
19 |
Correct |
460 ms |
22472 KB |
Output is correct |
20 |
Correct |
428 ms |
19332 KB |
Output is correct |
21 |
Correct |
469 ms |
19796 KB |
Output is correct |
22 |
Correct |
424 ms |
18884 KB |
Output is correct |
23 |
Correct |
149 ms |
19280 KB |
Output is correct |
24 |
Correct |
399 ms |
22316 KB |
Output is correct |
25 |
Correct |
11 ms |
892 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
19 ms |
2424 KB |
Output is correct |
29 |
Correct |
11 ms |
1400 KB |
Output is correct |
30 |
Correct |
3 ms |
376 KB |
Output is correct |
31 |
Correct |
4 ms |
504 KB |
Output is correct |
32 |
Correct |
4 ms |
504 KB |
Output is correct |
33 |
Correct |
3 ms |
376 KB |
Output is correct |
34 |
Correct |
11 ms |
1400 KB |
Output is correct |
35 |
Correct |
3 ms |
376 KB |
Output is correct |
36 |
Correct |
3 ms |
376 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
38 |
Correct |
3 ms |
376 KB |
Output is correct |
39 |
Correct |
3 ms |
376 KB |
Output is correct |
40 |
Correct |
323 ms |
20680 KB |
Output is correct |
41 |
Correct |
351 ms |
21184 KB |
Output is correct |
42 |
Correct |
327 ms |
21280 KB |
Output is correct |
43 |
Correct |
148 ms |
21864 KB |
Output is correct |
44 |
Correct |
253 ms |
21948 KB |
Output is correct |
45 |
Correct |
522 ms |
22712 KB |
Output is correct |
46 |
Correct |
370 ms |
22676 KB |
Output is correct |
47 |
Correct |
358 ms |
20664 KB |
Output is correct |
48 |
Correct |
182 ms |
19188 KB |
Output is correct |
49 |
Correct |
289 ms |
20260 KB |
Output is correct |
50 |
Correct |
368 ms |
22140 KB |
Output is correct |
51 |
Correct |
386 ms |
22888 KB |
Output is correct |