Advertisement
MinhNGUYEN2k4

Untitled

Mar 27th, 2021
187
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 200005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n, m, k;
  28. vector<int> a[N];
  29. int d[N];
  30. int g[N];
  31. int qu[N];
  32.  
  33. void readfile()
  34. {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(0);cout.tie(0);
  37.     if (fopen(Task".inp","r"))
  38.     {
  39.         freopen(Task".inp","r",stdin);
  40.         //freopen(Task".out","w",stdout);
  41.     }
  42.     cin >> n >> m >> k;
  43.     for(int i=1; i<=k; i++) cin >> qu[i];
  44.     for(int i=1; i<=m; i++)
  45.     {
  46.         int u, v;
  47.         cin >> u >> v;
  48.         a[u].pb(v);
  49.         a[v].pb(u);
  50.     }
  51. }
  52.  
  53. void dijkstra()
  54. {
  55.     priority_queue<ii, vii, greater<ii>> q;
  56.     q.push(ii(0,1));
  57.     for(int i=1; i<=n; i++) d[i] = inf, g[i] = inf;
  58.     d[1] = 0;
  59.     g[n] = 0;
  60.     while (q.size())
  61.     {
  62.         int u = q.top().se;
  63.         int du = q.top().fi;
  64.         q.pop();
  65.         if (du != d[u]) continue;
  66.         for(auto v : a[u])
  67.         {
  68.             if (d[v] > d[u] + 1)
  69.             {
  70.                 d[v] = d[u] + 1;
  71.                 q.push(ii(d[v],v));
  72.             }
  73.         }
  74.     }
  75.     q.push(ii(0,n));
  76.     while (q.size())
  77.     {
  78.         int u = q.top().se;
  79.         int du = q.top().fi;
  80.         q.pop();
  81.         if (g[u] != du) continue;
  82.         for(auto v : a[u])
  83.         {
  84.             if (g[v] > g[u] + 1)
  85.             {
  86.                 g[v] = g[u] + 1;
  87.                 q.push(ii(g[v],v));
  88.             }
  89.         }
  90.     }
  91. }
  92.  
  93. void proc()
  94. {
  95.     dijkstra();
  96.     int res = d[n];
  97.     int ans = minf;
  98.     int best = 0;
  99.     vector<ii> dat(k+1);
  100.     for(int i=1; i<=k; i++)
  101.     {
  102.         int u = qu[i];
  103.         dat.pb(ii(d[u]-g[u],u));
  104.     }
  105.     sort(dat.begin(),dat.end());
  106.     for(auto i : dat)
  107.     {
  108.         int x = i.se;
  109.         best = max(best, ans+g[x]);
  110.         ans = max(ans, d[x]);
  111.     }
  112.     cout << min(res,best+1);
  113. }
  114.  
  115. signed main()
  116. {
  117.     readfile();
  118.     proc();
  119.     return 0;
  120. }
  121.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement