Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- const int N = 1e5 + 2, oo = 2e9;
- vector <int> L[N];
- vector <int> from, dist;
- queue <int> q;
- int n;
- void Read()
- {
- ifstream fin("reinvent.in");
- int m, x;
- fin >> n >> m >> x;
- from = vector<int>(n + 1, 0);
- dist = vector<int>(n + 1, oo);
- while (m--)
- {
- int y, z;
- fin >> y >> z;
- L[y].push_back(z);
- L[z].push_back(y);
- }
- while (x--)
- {
- int vertex;
- fin >> vertex;
- dist[vertex] = 0;
- from[vertex] = vertex;
- q.push(vertex);
- }
- }
- void Solve()
- {
- int sol = oo;
- while (!q.empty())
- {
- int v = q.front();
- q.pop();
- for (auto next : L[v])
- {
- if (from[next] && from[v] && from[next] != from[v])
- sol = min(sol, dist[next] + dist[v] + 1);
- if (dist[next] > 1 + dist[v])
- {
- dist[next] = 1 + dist[v];
- from[next] = from[v];
- q.push(next);
- }
- }
- }
- ofstream fout("reinvent.out");
- fout << sol << "\n";
- }
- int main ()
- {
- Read();
- Solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement