本文主要是介绍分糖果(信息学奥赛一本通-T1380),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【题目描述】
童年的我们,将和朋友分享美好的事物作为自己的快乐。这天,C小朋友得到了Plenty of candies,将要把这些糖果分给要好的朋友们。已知糖果从一个人传给另一个人需要1 秒的时间,同一个小朋友不会重复接受糖果。由于糖果足够多,如果某时刻某小朋友接受了糖果,他会将糖果分成若干份,分给那些在他身旁且还没有得到糖果的小朋友们,而且自己会吃一些糖果。由于嘴馋,小朋友们等不及将糖果发完,会在得到糖果后边吃边发。每个小朋友从接受糖果到吃完糖果需要m秒的时间。那么,如果第一秒C小朋友开始发糖,第多少秒所有小朋友都吃完了糖呢?
【输入】
第一行为三个数n、p、c,为小朋友数、关系数和C小朋友的编号。
第二行为一个数m,表示小朋友吃糖的时间。
下面p行每行两个整数,表示某两个小朋友在彼此身旁。
【输出】
一个数,为所有小朋友都吃完了糖的时间。
【输入样例】
4 3 1
2
1 2
2 3
1 4【输出样例】
5
【源程序】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 10010
#define MOD 123
#define E 1e-6
using namespace std;
struct node{int pre;int next;int w;
}a[N*20];
int cnt;
int head[N],q[N*10];
int vis[N],f[N];
void add(int x,int y,int w)
{cnt++;a[cnt].pre=y;a[cnt].next=head[x];a[cnt].w=w;head[x]=cnt;cnt++;a[cnt].pre=x;a[cnt].next=head[y];a[cnt].w=w;head[y]=cnt;
}int main()
{int n,m,c,p;cin>>n>>p>>c>>m;for(int i=1;i<=p;i++){int x,y;cin>>x>>y;add(x,y,1);}memset(f,INF,sizeof(f));f[c]=0;vis[c]=1;int headd=1,tail=1;q[tail]=c;tail++;while(headd<tail){int x=q[headd];int k=head[x];while(k!=0){int y=a[k].pre;if(f[y]>f[x]+a[k].w){f[y]=f[x]+a[k].w;if(vis[y]==0){q[tail]=y;vis[y]=1;tail++;}}k=a[k].next;}headd++;}int maxx=-INF;for(int i=1;i<=n;i++)maxx=max(maxx,f[i]);cout<<maxx+m+1<<endl;return 0;
}
这篇关于分糖果(信息学奥赛一本通-T1380)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!