fork download
copy 
  1. #include<stdio.h>
  2. #include<queue>
  3. #include<algorithm>
  4. #define it register int
  5. #define ct const int 
  6. #define il inline
  7. using namespace std;
  8. const int N=1000005;
  9. const long long inf=1e18;
  10. typedef long long ll;
  11. int h[N],nxt[N],adj[N],w[N],a[N],p[N],p2[N],u,v,x,n,m,t,T,k,mindis,mx;
  12. ll d[N],d2[N],ans;
  13. bool inq[N];
  14. struct ky{
  15. 	int u;ll v;
  16. 	bool operator<(const ky&p)const{
  17. 		return v>p.v;
  18. 	}
  19. };
  20. priority_queue<ky> q;
  21. il void add(){nxt[++t]=h[u],h[u]=t,adj[t]=v,nxt[++t]=h[v],h[v]=t,adj[t]=u;}
  22. il void dij(ct s){
  23. 	for(it i=1;i<=n;++i) d[i]=inf,inq[i]=0;
  24. 	q.push((ky){s,0}),d[s]=0;
  25. 	register ky top;
  26. 	while(!q.empty()){
  27. 		top=q.top();q.pop();
  28. 		if(inq[top.u]) continue;
  29. 		inq[top.u]=true;
  30. 		for(it i=h[top.u];i;i=nxt[i])
  31. 			if(d[adj[i]]>top.v+1)
  32. 				d[adj[i]]=top.v+1,q.push((ky){adj[i],d[adj[i]]});
  33. 	}
  34. }
  35. il ll Min(ll p,ll q){return p<q?p:q;}
  36. il ll Max(ll p,ll q){return p>q?p:q;}
  37. namespace io{
  38. 	il char nc(){
  39. 		static char buf[100000],*p1=buf,*p2=buf;
  40. 		return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; 
  41. 	}
  42. 	template <class I> 
  43. 	il void fr(I &num){
  44. 		num=0;register char c=nc();it p=1;
  45. 		while(c<'0'||c>'9') c=='-'?p=-1,c=nc():c=nc();
  46. 		while(c>='0'&&c<='9') num=num*10+c-'0',c=nc();
  47. 		num*=p;
  48. 	} 
  49. }
  50. using io :: fr;
  51. struct kyl{
  52. 	ll d1,d2;
  53. }c[N];
  54. il bool cmp(kyl p,kyl q){return p.d1<q.d1||(p.d1==q.d1&&p.d2<q.d2);}
  55. int main(){
  56. 	fr(n),fr(m),fr(k);it i;
  57. 	for(i=1;i<=k;++i) fr(a[i]);
  58. 	for(i=1;i<=m;++i) fr(u),fr(v),add();
  59. 	dij(n);for(i=1;i<=n;++i) d2[i]=d[i];
  60. 	dij(1);mindis=d[n],mx=0;
  61. 	for(i=1;i<=k;++i) c[i]=(kyl){d[a[i]],d2[a[i]]};
  62. 	std::sort(c+1,c+1+k,cmp);
  63. 	//for(i=1;i<=k;++i) printf("%lld %lld\n",c[i].d1,c[i].d2);
  64. 	mx=c[k].d2;
  65. 	for(i=k-1;i;--i)
  66. 		ans=Max(ans,Min(mx,c[i].d2)+c[i].d1+1),mx=Max(c[i].d2,mx);
  67. 	printf("%lld",Min(ans,mindis));
  68. 	return 0;
  69. }
  70.  
Success #stdin #stdout 0s 4412KB
comments (?)
stdin
copy 
5 4 2
2 4
1 2
2 3
3 4
4 5
stdout
copy 
3
https://ideone.com/F6Dqr2
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!