比赛 至少完成十道练习 评测结果 AAAAAAAAAA
题目名称 分糖果 最终得分 100
用户昵称 Mealy 运行时间 1.345 s
代码语言 C++ 内存使用 1.84 MiB
提交时间 2017-05-23 15:20:15
显示代码纯文本
//2119
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>

const int nmax = 100010;
const int INF = 0x3f3f3f3f;

using namespace std;

int N,P,C,cost;
int u,v;
int d[nmax] = {0};
vector<int > G[nmax];

void PreDo(){
	scanf("%d%d%d%d",&N,&P,&C,&cost);
	memset(d,0,sizeof(d));
	for(int i = 1;i <= P;i++){
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
}

void SPFA(){
	queue<int > Q;
	bool inqueue[nmax];
	memset(inqueue,0,sizeof(inqueue));
	
	
	Q.push(C);
	inqueue[C] = 1;
	for(int i = 0;i <= N;i++){
		d[i]=INF;
	}
	d[C]=0;	
	
	while(!Q.empty()){
		int tmpx = Q.front();
		Q.pop();
		inqueue[tmpx]=0;
		for(int i = 0;i < G[tmpx].size();i++){
			int v = G[tmpx][i];
			if(d[v] > d[tmpx] + 1){
				d[v] = d[tmpx] + 1;
				if(!inqueue[v]){
					Q.push(v);
					inqueue[v] = 1;
				}
			}
		}
	}
}
	
void Cal(){
	SPFA();
	int ans=0;
	for(int i = 1;i <= N;i++){
		ans = max(ans,d[i]);
	}
	printf("%d",ans+cost+1);
}

int main(){
	freopen("dividecandy.in","r",stdin);
	freopen("dividecandy.out","w",stdout);
	PreDo();
	Cal();
	return 0;
}