大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
分糖果
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行每行两个整数，表示某两个小朋友在彼此身旁。
第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
//思路就是找出与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.net/117097.html原文链接：https://javaforall.net
