C++14(g++5.4) 解法, 执行用时: 54ms, 内存消耗: 8412K, 提交时间: 2019-08-15 20:54:29

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
#define inf 0x3f3f3f3f
int n,m,k,s,cnt;
int a[maxn],ans[maxn];
vector<int> G[maxn];

void bfs(){
	queue<int> que;
	while(!que.empty())que.pop();
	que.push(s);
	while(!que.empty()){
		int p=que.front();
		que.pop();
		for(int i=0;i<G[p].size();i++){
			int q=G[p][i];
			if(!ans[q]){
				ans[q]=ans[p]+1;
				que.push(q);
			}
		}
	}
}
int main(){
ios::sync_with_stdio(0);
  while(cin>>n>>m>>k>>s){
  	memset(G,0,sizeof(G));
  	for(int i=1;i<=k;i++)cin>>a[i];
  	for(int i=1;i<=m;i++){
  		int x,y;
  		cin>>x>>y;
  		G[x].push_back(y);
  		G[y].push_back(x);
	  }
	  memset(ans,0,sizeof(ans));
	  bfs();
	  int res=inf;
	  for(int i=1;i<=k;i++){
	  	if(ans[a[i]]&&ans[a[i]]<=i)
	  	res=min(res,i);
	  }
	  if(res==inf)res=ans[a[k]];
	  cout<<res<<endl;
  }
}

C++11(clang++ 3.9) 解法, 执行用时: 45ms, 内存消耗: 3452K, 提交时间: 2017-12-16 01:12:47

#include<bits/stdc++.h>
#define lowbit(o) o&-o
#define N 200005
#define inf 1000000007
using namespace std;
int a[N];
int i,j,k,Next[N],bb,q[N],to[N],last[N],tot,b[N],x,y,n,m,s;
inline void add(int x,int y) {
	Next[++tot]=last[x]; last[x]=tot; to[tot]=y;
}
int main() {
	while (scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF) {
		for (i=1;i<=n;i++) last[i]=0;
		tot=0;
		for (i=1;i<=k;i++) scanf("%d",&a[i]);
		for (i=1;i<=m;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
		for (i=1;i<=n;i++) b[i]=inf;
		b[s]=0;
		int l=0,r=1; q[1]=s;
		while (l<r) {
			int k=q[++l];
			for (int i=last[k];i;i=Next[i]) if (b[to[i]]==inf) b[to[i]]=b[k]+1,q[++r]=to[i];
		}
		bb=0;
		for (i=1;i<=k;i++) if (b[a[i]]<=i) {
			bb=1; printf("%d\n",i); break;
		}
		if (!bb) printf("%d\n",b[a[k]]);
	}
}