首页 > 代码库 > 分糖果
分糖果
分糖果
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
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。