Advertisement
nicuvlad76

Untitled

Jan 13th, 2021
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.03 KB | None | 0 0
  1. #include <fstream>
  2. #include <iostream>
  3. #include <vector>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. const int N = 1e5 + 2, oo = 2e9;
  9.  
  10. vector <int> L[N];
  11. vector <int> from, dist;
  12. queue <int> q;
  13. int n;
  14.  
  15. void Read()
  16. {
  17. ifstream fin("reinvent.in");
  18. int m, x;
  19. fin >> n >> m >> x;
  20. from = vector<int>(n + 1, 0);
  21. dist = vector<int>(n + 1, oo);
  22. while (m--)
  23. {
  24. int y, z;
  25. fin >> y >> z;
  26. L[y].push_back(z);
  27. L[z].push_back(y);
  28. }
  29. while (x--)
  30. {
  31. int vertex;
  32. fin >> vertex;
  33. dist[vertex] = 0;
  34. from[vertex] = vertex;
  35. q.push(vertex);
  36. }
  37. }
  38.  
  39. void Solve()
  40. {
  41. int sol = oo;
  42. while (!q.empty())
  43. {
  44. int v = q.front();
  45. q.pop();
  46. for (auto next : L[v])
  47. {
  48. if (from[next] && from[v] && from[next] != from[v])
  49. sol = min(sol, dist[next] + dist[v] + 1);
  50. if (dist[next] > 1 + dist[v])
  51. {
  52. dist[next] = 1 + dist[v];
  53. from[next] = from[v];
  54. q.push(next);
  55. }
  56. }
  57. }
  58. ofstream fout("reinvent.out");
  59. fout << sol << "\n";
  60. }
  61.  
  62. int main ()
  63. {
  64. Read();
  65. Solve();
  66. return 0;
  67. }
  68.  
  69.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement