当前位置:网站首页>分糖果
分糖果
2022-07-06 12:55:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
分糖果
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 18 Accepted Submission(s) : 3
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
童年的我们将和朋友分享美好的事物作为自己的快乐。这天,C小朋友得到了糖果,将要把这些糖果分给要好的朋友们。已知糖果从一个人传给还有一个人须要1秒的时间,同一个小朋友不会反复接受糖果。因为糖果足够多,假设某时刻某小朋友接受了糖果。他会将糖果分成若干份,分给那些在他身旁且还没有得到糖果的小朋友们,并且自己会吃一些糖果。因为嘴馋,小朋友们等不及将糖果发完,会在得到糖果后边吃边发。每一个小朋友从接受糖果到吃完糖果须要m秒的时间。那么,假设第一秒C小朋友開始发糖,第几秒全部小朋友都吃完了糖呢?
Input
输入有多组数据,每组数据第1行为三个数n(<=10000),p(<=600000),c为小朋友数,关系数和C小朋友的编号。 第2行为一个数m(<=8000),表示小朋友吃糖的时间。 以下p行每行两个整数,表示某两个小朋友在彼此身旁。
Output
对于每组输入输出一个单独的整数表示从Ts到Te的最小总费用。数据保证至少存在一条道路。
Sample Input
4 3 1
2
1 2
2 3
1 4
Sample Output
5
Hint
第一秒,糖在1手上。第二秒,糖传到了2、4的手中。第三秒。糖传到了3的手中,此时1吃完了。第四秒,2、4吃完了。第五秒。3吃完了。所以答案是5。
Author
HYNU
//思路就是找出与1相隔最远的那个点到1的距离,首先把每一条路径的权值都标记为1。找出最远点加上m就是答案。由于最后一个人吃糖须要m时间,假设最后这个这个人都吃完了,那他前面的人肯定已经吃完了。 在找的时候用到的是图的广度优先搜索,由于n非常大。那么使用vector动态数组来存储边。
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
vector<int>num[10001];
queue<int>q;
int vis[10001],f[10001];
void bfs()
{
int i,t;
while(!q.empty())
{
t=q.front();
q.pop();
for(i=0;i<num[t].size();i++)
{
if(!vis[num[t][i]])
{
vis[num[t][i]]=1;
f[num[t][i]]=f[t]+1;
q.push(num[t][i]);
}
}
}
}
int main()
{
int n,p,c,m,i,a,b;
while(scanf("%d%d%d%d",&n,&p,&c,&m)!=EOF)
{
for(i=0;i<=n;i++)
num[i].clear();
memset(vis,0,sizeof(vis));
memset(f,0,sizeof(f));
while(!q.empty()) q.pop();
for(i=0;i<p;i++)
{
scanf("%d%d",&a,&b);
num[a].push_back(b);
num[b].push_back(a);
}
q.push(c);
vis[c]=1;
f[c]=1;
bfs();
int ans=0;
for(i=1;i<=n;i++)
{
if(f[i]>ans) ans=f[i];
//printf("%d\n",f[i]);
}
printf("%d\n",ans+m);
}
return 0;
}
版权声明:本文博主原创文章。博客,未经同意不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117097.html原文链接:https://javaforall.cn
边栏推荐
- Nodejs教程之Expressjs一篇文章快速入门
- Aiko ai Frontier promotion (7.6)
- Spiral square PTA
- Swagger UI tutorial API document artifact
- The mail command is used in combination with the pipeline command statement
- 【OpenCV 例程200篇】220.对图像进行马赛克处理
- How to implement common frameworks
- Web开发小妙招:巧用ThreadLocal规避层层传值
- 'class file has wrong version 52.0, should be 50.0' - class file has wrong version 52.0, should be 50.0
- OAI 5g nr+usrp b210 installation and construction
猜你喜欢
Mécanisme de fonctionnement et de mise à jour de [Widget Wechat]
2017 8th Blue Bridge Cup group a provincial tournament
968 edit distance
Aike AI frontier promotion (7.6)
PHP online examination system version 4.0 source code computer + mobile terminal
Reviewer dis's whole research direction is not just reviewing my manuscript. What should I do?
use. Net drives the OLED display of Jetson nano
Reinforcement learning - learning notes 5 | alphago
硬件开发笔记(十): 硬件开发基本流程,制作一个USB转RS232的模块(九):创建CH340G/MAX232封装库sop-16并关联原理图元器件
2022 fields Award Announced! The first Korean Xu Long'er was on the list, and four post-80s women won the prize. Ukrainian female mathematicians became the only two women to win the prize in history
随机推荐
'class file has wrong version 52.0, should be 50.0' - class file has wrong version 52.0, should be 50.0
[wechat applet] operation mechanism and update mechanism
MLP (multilayer perceptron neural network) is a multilayer fully connected neural network model.
Entity alignment two of knowledge map
Statistical inference: maximum likelihood estimation, Bayesian estimation and variance deviation decomposition
审稿人dis整个研究方向已经不仅仅是在审我的稿子了怎么办?
C language games - three chess
##无yum源安装spug监控
No Yum source to install SPuG monitoring
1_ Introduction to go language
Is it safe to open an account in flush? Which securities company is good at opening an account? Low handling charges
【mysql】游标的基本使用
Le langage r visualise les relations entre plus de deux variables de classification (catégories), crée des plots Mosaiques en utilisant la fonction Mosaic dans le paquet VCD, et visualise les relation
3D人脸重建:从基础知识到识别/重建方法!
Variable star --- article module (1)
2017 8th Blue Bridge Cup group a provincial tournament
js之遍历数组、字符串
document.write()的用法-写入文本——修改样式、位置控制
966 minimum path sum
Reference frame generation based on deep learning