Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <cstring>
- #include <iomanip>
- #include <set>
- using namespace std;
- vector<vector<int> > g1, g2;
- int f = 0;
- int a, b;
- long long sz;
- vector<long long> dist1, dist2, dist3;
- void dfs1(int v, int p, long long s)
- {
- //used[v] = 1;
- dist1[v] = min(dist1[v], s);
- for (int i = 0; i < g2[v].size() ; i++)
- {
- int to = g2[v][i];
- if (to != p && dist1[v] + 1 < dist1[to])
- dfs1(to, v, s + 1);
- }
- }
- void dfs2(int v, int p, long long s)
- {
- //used[v] = 1;
- dist2[v] = min(dist2[v], s);
- for (int i = 0; i < g1[v].size(); i++)
- {
- int to = g1[v][i];
- if (to != p && dist2[v] + 1 < dist2[to])
- dfs2(to, v, s + 1);
- }
- }
- void dfs3(int v, int p, long long s)
- {
- //used[v] = 1;
- dist3[v] = min(dist3[v], s);
- for (int i = 0; i < g1[v].size(); i++)
- {
- int to = g1[v][i];
- if (to != p && dist3[v] + 1 < dist3[to])
- dfs3(to, v, s + 1);
- }
- }
- int main()
- {
- int n, m;
- cin >> n >> m;
- cin >> a >> b;
- g1.resize(n + 1);
- g2.resize(n + 1);
- int x, y;
- for (int i = 0; i < m; i++)
- {
- cin >> x >> y;
- g1[y].push_back(x);
- g2[x].push_back(y);
- }
- long long ans = 1e18;
- //used.assign(n + 1, 0);
- dist1.assign(n + 1, n * n);
- dist2.assign(n + 1, n * n);
- dist3.assign(n + 1, n * n);
- dfs1(0, -1, 0);
- //used.assign(n + 1, 0);
- dfs2(a, -1, 0);
- //used.assign(n + 1, 0);
- dfs3(b, -1, 0);
- for (int i = 0; i <= n; i++)
- ans = min(ans, dist1[i] + dist2[i] + dist3[i]);
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement