Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <vector>
- #define c_boost std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr)
- using namespace std;
- using graph=vector <vector <int>>;
- vector <bool> used;
- vector <int> reverseEdges;
- graph g;
- graph gT;
- void BFS(int start) {
- queue <int> q;
- q.push(start);
- while (!q.empty()) {
- int from = q.front();
- q.pop();
- used[from] = true;
- for (int to: g[from]) {
- reverseEdges[to] = min(reverseEdges[to], reverseEdges[from]);
- if (!used[to]) {
- q.push(to);
- }
- }
- for (int backTo : gT[from]) {
- reverseEdges[backTo] = min(reverseEdges[backTo], reverseEdges[from] + 1);
- if (!used[backTo]) {
- q.push(backTo);
- }
- }
- }
- }
- int main() {
- c_boost;
- int n, m, start, end;
- cout << "Введите {n}, {m}, {start}, {end}\n";
- cin >> n >> m >> start >> end;
- used.assign(n, false);
- reverseEdges.assign(n, 0);
- g = graph(n);
- gT = graph(n);
- for (int i = 0; i < m; ++i) {
- int from, to;
- cin >> from >> to;
- --from;
- --to;
- g[from].push_back(to);
- gT[to].push_back(from);
- }
- BFS(start - 1);
- cout << reverseEdges[end - 1];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement