Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- #include <climits>
- #include <set>
- #include <queue>
- using namespace std;
- struct Vertex {
- int index;
- int number = -1;
- vector<int> neighbours;
- bool isFinish = false;
- Vertex(int index) : index(index) {}
- void add(int neighbour) {
- neighbours.push_back(neighbour);
- }
- };
- vector<Vertex*> vertexes;
- int getLen(int start) {
- priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> next;
- //currLen, index, addedInSearchFor
- next.push({ 0, {start, 0} });
- set<int> inCurrSearch;
- int currSearch = 0;
- while (!next.empty()) {
- int currLen = next.top().first;
- int currIndex = next.top().second.first;
- next.pop();
- if (inCurrSearch.find(currIndex) != inCurrSearch.end())
- continue;
- inCurrSearch.insert(currIndex);
- if (vertexes[currIndex]->number == currSearch) {
- currSearch++;
- inCurrSearch.clear();
- if (vertexes[currIndex]->isFinish) {
- return currLen;
- }
- }
- for (int neighbour : vertexes[currIndex]->neighbours) {
- if (vertexes[neighbour]->number <= currSearch)
- next.push({ currLen + 1, {neighbour, currSearch} });
- }
- while (!next.empty() && next.top().second.second < currSearch)
- next.pop();
- }
- return -1;
- }
- int main() {
- int n, m, a, b, k, start;
- cin >> n >> m;
- for (int i = 0; i < n; i++) {
- vertexes.push_back(new Vertex(i));
- }
- for (int i = 0; i < m; i++) {
- cin >> a >> b;
- if (a == b)
- {
- continue;
- }
- vertexes[a]->add(b);
- }
- cin >> k;
- for (int i = 0; i < k; i++) {
- cin >> a;
- vertexes[a]->number = i;
- if (i == 0)
- start = a;
- }
- vertexes[a]->isFinish = true;
- cout << getLen(start);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment