# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
90795 | FutymyClone | 007 (CEOI14_007) | C++14 | 291 ms | 17500 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, s, d, a, b, d1[N], d2[N];
vector <int> g[N];
void bfs1(){
memset(d1, 0x3f, sizeof(d1)); queue <int> q;
d1[a] = 0; q.push(a);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto v: g[u]) {
if (d1[v] > d1[u] + 1) {
d1[v] = d1[u] + 1;
q.push(v);
}
}
}
}
void bfs2(){
memset(d2, 0x3f, sizeof(d2)); queue <int> q;
d2[b] = 0; q.push(b);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto v: g[u]) {
if (d2[v] > d2[u] + 1) {
d2[v] = d2[u] + 1;
q.push(v);
}
}
}
}
int main(){
scanf("%d %d", &n, &m);
scanf("%d %d %d %d", &s, &d, &a, &b);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
g[u].push_back(v); g[v].push_back(u);
}
bfs1(); bfs2();
printf("%d", max(min(d1[d] - d1[s], d2[d] - d2[s]), -1));
return 0;
}
/*
6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4
6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |