当前位置:网站首页>Divide candy
Divide candy
2022-07-06 21:14:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
Divide candy
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
In childhood, we will share good things with our friends as our own happiness . On the day ,C The children got candy , I'm going to give these sweets to my best friends . It is known that candy is passed from one person to another who needs 1 The second time , The same child will not accept candy repeatedly . Because there are enough sweets , Suppose a child accepts candy at some time . He will divide the candy into several parts , Give it to the children who are beside him and haven't got candy yet , And I will eat some candy . Because of greediness , The children can't wait to send out the candy , Will eat and distribute after getting candy . Every child needs... From accepting candy to eating it m The second time . that , Suppose the first second C The children began to send sugar , In a few seconds, all the children finished eating sugar ?
Input
Input has multiple sets of data , The data of each group is no 1 Act three numbers n(<=10000),p(<=600000),c Count the children , Relationship number and C Number... Children . The first 2 Behavior a number m(<=8000), It means the time for children to eat sugar . following p Two integers per line , It means that two children are beside each other .
Output
For each set of inputs, output a separate integer representation from Ts To Te The minimum total cost of . Data guarantees that there is at least one path .
Sample Input
4 3 1
2
1 2
2 3
1 4
Sample Output
5
Hint
The first second , Sugar in 1 On hand . The second seconds , The sugar reached 2、4 In the hands of . The third second . The sugar reached 3 In the hands of , here 1 I'm full . The fourth second ,2、4 I'm full . The fifth second .3 I'm full . So the answer is 5.
Author
HYNU
// The idea is to find out and 1 From the farthest point to 1 Distance of , First, mark the weight of each path as 1. Find the farthest point and add m That's the answer. . Because the last person to eat sugar needs m Time , Suppose this person has finished eating in the end , Then the person in front of him must have finished . When searching, we use the breadth first search of graph , because n A very large . So use vector Dynamic array to store edges .
#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;
}
Copyright notice : This article is the original article of the blogger . Blog , Do not reprint without permission .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/117097.html Link to the original text :https://javaforall.cn
边栏推荐
- 防火墙基础之外网服务器区部署和双机热备
- @Detailed differences among getmapping, @postmapping and @requestmapping, with actual combat code (all)
- Why do job hopping take more than promotion?
- What is the difference between procedural SQL and C language in defining variables
- Seven original sins of embedded development
- This year, Jianzhi Tencent
- New database, multidimensional table platform inventory note, flowus, airtable, seatable, Vig table Vika, Feishu multidimensional table, heipayun, Zhixin information, YuQue
- js中,字符串和数组互转(一)——字符串转为数组的方法
- C # use Oracle stored procedure to obtain result set instance
- 华为设备命令
猜你喜欢
Common English vocabulary that every programmer must master (recommended Collection)
性能测试过程和计划
SAP UI5 框架的 manifest.json
Swagger UI教程 API 文档神器
The biggest pain point of traffic management - the resource utilization rate cannot go up
Pinduoduo lost the lawsuit, and the case of bargain price difference of 0.9% was sentenced; Wechat internal test, the same mobile phone number can register two account functions; 2022 fields Awards an
3D face reconstruction: from basic knowledge to recognition / reconstruction methods!
请问sql group by 语句问题
[200 opencv routines] 220 Mosaic the image
Why do job hopping take more than promotion?
随机推荐
[in depth learning] pytorch 1.12 was released, officially supporting Apple M1 chip GPU acceleration and repairing many bugs
Reflection operation exercise
Forward maximum matching method
Spiral square PTA
R language visualizes the relationship between more than two classification (category) variables, uses mosaic function in VCD package to create mosaic plots, and visualizes the relationship between tw
华为设备命令
Reference frame generation based on deep learning
15 millions d'employés sont faciles à gérer et la base de données native du cloud gaussdb rend le Bureau des RH plus efficace
新型数据库、多维表格平台盘点 Notion、FlowUs、Airtable、SeaTable、维格表 Vika、飞书多维表格、黑帕云、织信 Informat、语雀
Data Lake (VIII): Iceberg data storage format
No Yum source to install SPuG monitoring
el-table表格——获取单击的是第几行和第几列 & 表格排序之el-table与sort-change、el-table-column与sort-method & 清除排序-clearSort
In JS, string and array are converted to each other (II) -- the method of converting array into string
ICML 2022 | flowformer: task generic linear complexity transformer
LLVM之父Chris Lattner:为什么我们要重建AI基础设施软件
JS according to the Chinese Alphabet (province) or according to the English alphabet - Za sort &az sort
OSPF多区域配置
js之遍历数组、字符串
What are RDB and AOF
Reinforcement learning - learning notes 5 | alphago