Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 200005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- int n, m, k;
- vector<int> a[N];
- int d[N];
- int g[N];
- int qu[N];
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> n >> m >> k;
- for(int i=1; i<=k; i++) cin >> qu[i];
- for(int i=1; i<=m; i++)
- {
- int u, v;
- cin >> u >> v;
- a[u].pb(v);
- a[v].pb(u);
- }
- }
- void dijkstra()
- {
- priority_queue<ii, vii, greater<ii>> q;
- q.push(ii(0,1));
- for(int i=1; i<=n; i++) d[i] = inf, g[i] = inf;
- d[1] = 0;
- g[n] = 0;
- while (q.size())
- {
- int u = q.top().se;
- int du = q.top().fi;
- q.pop();
- if (du != d[u]) continue;
- for(auto v : a[u])
- {
- if (d[v] > d[u] + 1)
- {
- d[v] = d[u] + 1;
- q.push(ii(d[v],v));
- }
- }
- }
- q.push(ii(0,n));
- while (q.size())
- {
- int u = q.top().se;
- int du = q.top().fi;
- q.pop();
- if (g[u] != du) continue;
- for(auto v : a[u])
- {
- if (g[v] > g[u] + 1)
- {
- g[v] = g[u] + 1;
- q.push(ii(g[v],v));
- }
- }
- }
- }
- void proc()
- {
- dijkstra();
- int res = d[n];
- int ans = minf;
- int best = 0;
- vector<ii> dat(k+1);
- for(int i=1; i<=k; i++)
- {
- int u = qu[i];
- dat.pb(ii(d[u]-g[u],u));
- }
- sort(dat.begin(),dat.end());
- for(auto i : dat)
- {
- int x = i.se;
- best = max(best, ans+g[x]);
- ans = max(ans, d[x]);
- }
- cout << min(res,best+1);
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement