比赛 |
至少完成十道练习 |
评测结果 |
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;
}