SHARE
TWEET

Untitled

a guest Feb 17th, 2020 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ull = unsigned long long;
  6. using ld = long double;
  7. #define all(x) x.begin(), x.end()
  8.  
  9. template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
  10. template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}
  11.  
  12. #define int ll
  13.  
  14. const int MAXN = 2e5 + 10;
  15. vector<int> g[MAXN];
  16. int n, m, k;
  17. vector<int> a;
  18.  
  19. void read() {
  20.     cin >> n >> m >> k;
  21.     a.resize(k);
  22.     for (auto &i : a) {
  23.         cin >> i;
  24.         i--;
  25.     }
  26.     for (int i = 0; i < m; i++) {
  27.         int u, v;
  28.         cin >> u >> v;
  29.         u--;
  30.         v--;
  31.         g[u].push_back(v);
  32.         g[v].push_back(u);
  33.     }
  34. }
  35.  
  36. int d_s[MAXN], d_t[MAXN];
  37. queue<int> q;
  38.  
  39. void build() {
  40.     for (int i = 0; i < n; i++)
  41.         d_s[i] = n + 1;
  42.     d_s[0] = 0;
  43.     q.push(0);
  44.     while (!q.empty()) {
  45.         int v = q.front();
  46.         q.pop();
  47.         for (auto i : g[v]) {
  48.             if (d_s[i] != n + 1) continue;
  49.             d_s[i] = d_s[v] + 1;
  50.             q.push(i);
  51.         }
  52.     }
  53.  
  54.     for (int i = 0; i < n; i++)
  55.         d_t[i] = n + 1;
  56.     d_t[n - 1] = 0;
  57.     q.push(n - 1);
  58.     while (!q.empty()) {
  59.         int v = q.front();
  60.         q.pop();
  61.         for (auto i : g[v]) {
  62.             if (d_t[i] != n + 1) continue;
  63.             d_t[i] = d_t[v] + 1;
  64.             q.push(i);
  65.         }
  66.     }
  67. }
  68.  
  69. int ans;
  70.  
  71. void relax(int u, int v) {
  72.     int fans = d_s[n - 1];
  73.     chkmin(fans, 1 + d_s[u] + d_t[v]);
  74.     chkmin(fans, 1 + d_s[v] + d_t[u]);
  75.     chkmax(ans, fans);
  76. }
  77.  
  78. void solve() {
  79.     /*for (int i = 0; i < n; i++)
  80.         cout << d_s[i] << " ";
  81.     cout << endl;
  82.     for (int i = 0; i < n; i++)
  83.         cout << d_t[i] << " ";
  84.     cout << endl;*/
  85.  
  86.     set<int> used;
  87.     for (auto i : a)
  88.         used.insert(i);
  89.     for (auto i : a) {
  90.         for (auto j : g[i]) {
  91.             if (used.count(j)) {
  92.                 cout << d_s[n - 1] << endl;
  93.                 exit(0);
  94.             }
  95.         }
  96.     }
  97.  
  98.     ans = 0;
  99.     sort(all(a), [&] (int i, int j) {return d_s[i] < d_s[j];});
  100.    
  101.     for (int i = 0; i < k; i++) {
  102.         for (int j = i + 1; j < k && j - i <= 100; j++) {
  103.             relax(a[i], a[j]);
  104.         }
  105.     }
  106. }
  107.  
  108. void run() {
  109.     build();
  110.     solve();
  111. }
  112.  
  113. void write() {
  114.     cout << ans << endl;
  115. }
  116.  
  117. signed main() {
  118.     ios_base::sync_with_stdio(0);
  119.     cin.tie(0);
  120.     cout.tie(0);
  121.     read();
  122.     run();
  123.     write();
  124.     return 0;
  125. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top