#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
int n, m;
vector<vector<pair<int, int>>> adj;
void dijkstras(vector<int> &parent, vector<long long> &dist, int start) {
priority_queue<pair<int, int>> pq;
pq.push({0, start});
while (!pq.empty()) {
int x = pq.top().second;
pq.pop();
for (auto e : adj[x]) {
int w = e.second;
if (w + dist[x] < dist[e.first]) {
parent[e.first] = x;
dist[e.first] = dist[x]+w;
pq.push({-dist[e.first], e.first});
}
}
}
}
int main() {
cin >> n >> m;
adj.resize(n+1);
int s, t, u, v;
cin >> s >> t >> u >> v;
for (int i = 0; i < m; i++) {
int x, y, w;
cin >> x >> y >> w;
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
vector<int> p(n+1);
p[s] = s;
vector<long long> d(n+1, INF);
d[s] = 0;
dijkstras(p, d, s);
vector<int> path;
int x = t;
while (x != s) {
path.push_back(x);
x = p[x];
}
path.push_back(s);
vector<int> from_u(n+1);
vector<long long> du(n+1, INF);
du[u] = 0;
dijkstras(from_u, du, u);
vector<int> from_v(n+1);
vector<long long> dv(n+1, INF);
dv[v] = 0;
dijkstras(from_v, dv, v);
long long ans = du[v];
long long mnu = INF, mnv = INF;
for (int i = 0; i < path.size(); i++) {
mnu = min(mnu, du[path[i]]);
mnv = min(mnv, dv[path[i]]);
ans = min(ans, mnu+mnv);
}
cout << ans << '\n';
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < path.size(); i++) {
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
221 ms |
17956 KB |
Output is correct |
2 |
Correct |
273 ms |
16880 KB |
Output is correct |
3 |
Correct |
319 ms |
17520 KB |
Output is correct |
4 |
Incorrect |
235 ms |
17896 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
343 ms |
17100 KB |
Output is correct |
2 |
Correct |
247 ms |
16932 KB |
Output is correct |
3 |
Correct |
277 ms |
17188 KB |
Output is correct |
4 |
Correct |
271 ms |
16964 KB |
Output is correct |
5 |
Correct |
232 ms |
17152 KB |
Output is correct |
6 |
Correct |
251 ms |
17256 KB |
Output is correct |
7 |
Correct |
250 ms |
17264 KB |
Output is correct |
8 |
Correct |
295 ms |
17080 KB |
Output is correct |
9 |
Correct |
275 ms |
17236 KB |
Output is correct |
10 |
Correct |
292 ms |
16932 KB |
Output is correct |
11 |
Correct |
109 ms |
11776 KB |
Output is correct |
12 |
Correct |
251 ms |
17456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
1524 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
221 ms |
17956 KB |
Output is correct |
2 |
Correct |
273 ms |
16880 KB |
Output is correct |
3 |
Correct |
319 ms |
17520 KB |
Output is correct |
4 |
Incorrect |
235 ms |
17896 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |