分糖果(BFS)
2024-09-07 05:06:33
题目描述
童年的我们,将和朋友分享美好的事物作为自己的快乐。这天,C小朋友得到了糖果,将要把这些糖果分给要好的朋友们。已知糖果从一个人传给另一个人需要1秒的时间,同一个小朋友不会重复接受糖果。由于糖果足够多,如果某时刻某小朋友接受了糖果,他会将糖果分成若干份,分给哪些在他身旁且还没有得到糖果的小朋友们,而且自己会吃一些糖果。由于嘴馋,小朋友们等不及将糖果发完,会在得到糖果后边吃边发。每个小朋友从接收糖果到吃完糖果需要m秒的时间。那么,如果第1秒C小朋友开始发糖,第几秒所有小朋友都吃完了糖呢?
输入
第1行为三个整数n、p、c,为小朋友数、关系数和C小朋友的编号。(1<=n<=100000)
第2行为一个数m,表示小朋友吃糖的时间。
下面p行每行两个整数,表示某两个小朋友在彼此身旁。
输出
一个整数,为所有小朋友都吃完了糖的时间。
样例输入
样例输出
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
const int INF=0x3f3f3f3f;
typedef long long LL;
using namespace std; struct node
{
int num;
int step;
};
int MAX;
vector<int> E[];
bool vis[];
queue<node> qe; void BFS()
{
while(!qe.empty())
{
node now=qe.front();
qe.pop();
for(int i=;i<E[now.num].size();i++)
{
node to;
to.num=E[now.num][i];
to.step=now.step+;
if(!vis[to.num])
{
vis[to.num]=true;
qe.push(to);
if(to.step>MAX)
MAX=to.step;
}
}
}
} int main()
{
#ifdef DEBUG
freopen("sample.txt","r",stdin);
#endif int n,p,c,m;
scanf("%d %d %d %d",&n,&p,&c,&m);
for(int i=;i<=p;i++)
{
int a,b;
scanf("%d %d",&a,&b);
E[a].push_back(b);
E[b].push_back(a);
}
node st;
st.num=c;
st.step=;
qe.push(st);
BFS();
printf("%d\n",MAX+m); return ;
}
-
最新文章
- CH模拟赛 还教室
- Azure PowerShell (2) 修改Azure订阅名称
- LinkedList实现队列和堆栈的代码
- c语言问卷调查
- Oracle PL/SQL块
- Creating List Item in Oracle D2k
- codeforces 192 D
- Android.mk文件语法规范 原文
- Unity3d不支持vistual studio2012?用vs2012打开unity c#脚本进行编码的方法。
- ACM1024动态规划
- Entity Framework with MySQL 学习笔记一(拦截)
- C语言程序的结构分析
- 【C++知识汇总】运营商 &;amp; 运算符重载
- 201521123017 《Java程序设计》第2周学习总结
- the c programing language 学习过程8
- DirectX11--HLSL中矩阵的内存布局和mul函数探讨
- devexpress总结 accordionControl 加载panelcontrol 的快捷方式
- leetcode 199. Binary Tree Right Side View 、leetcode 116. Populating Next Right Pointers in Each Node 、117. Populating Next Right Pointers in Each Node II
- vue--v-model表单控件绑定
- 【Ansible 文档】【译文】Windows 支持