【Tyvj1083】分糖果

描述 Description

童年的我们,将和朋友分享美好的事物作为自己的快乐。这天,C 小朋友得到了 Plenty of candies,将要把这些糖果分给要好的朋友们。已知糖果从一个人传给另一个人需要 1 秒的时间,同一个小朋友不会重复接受糖果。由于糖果足够多,如果某时刻某小朋友接受了糖果,他会将糖果分成若干份,分给那些在他身旁且还没有得到糖果的小朋友们,而且自己会吃一些糖果。由于嘴馋,小朋友们等不及将糖果发完,会在得到糖果后边吃边发。每个小朋友从接受糖果到吃完糖果需要 m 秒的时间。那么,如果第一秒 C 小朋友开始发糖,第多少秒所有小朋友都吃完了糖呢?

输入格式 InputFormat

第一行为三个数 n、p、c,为小朋友数、关系数和 C 小朋友的编号。

第二行为一个数 m,表示小朋友吃糖的时间。

下面 p 行每行两个整数,表示某两个小朋友在彼此身旁。

输出格式 OutputFormat

一个数,为所有小朋友都吃完了糖的时间。

样例输入 SampleInput

4 3 1
2
1 2
2 3
1 4

样例输出 SampleOutput

5


Tyvj 1083


代码 Code

水。注意数据范围。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct rela
{
    int x,y;
}a[200001];
bool b[100001];
int f[1000001];
int c[100001];
int tim[1000001];
int i,j,t,n,m,p,s,l,r,k,ans;
bool comp(rela a,rela b)
{
    if (a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}
void TEST()
{
    int i,j,t;
    for (i=1;i<=p;i++) cout<<a[i].x<<endl;
    for (i=0;i<=r;i++) cout<<i<<""<<f[i]<<" "<<tim[i]<<endl; 
}
int main()
{
    memset(b,0,sizeof(b));
    scanf("%d%d%d",&n,&p,&s);
    scanf("%d",&m);
    for (i=1;i<=p;i++) 
    {
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i+p].x=a[i].y;a[i+p].y=a[i].x;
    }
    p*=2;
    sort(a+1,a+p+1,comp);
    for (i=1;i<=p;i++) if (a[i].x!=a[i-1].x) c[a[i].x]=i;
    l=0;r=0;tim[0]=m+1;f[0]=s;
    while (r>=l)
    {
        t=f[l];
        for (i=c[t];a[i].x==t;i++) if (b[a[i].y]==false)
        {
            f[++r]=a[i].y;
            tim[r]=tim[l]+1;
            b[f[r]]=true;
        }
        l++;
    }
    printf("%d",tim[r]);
    return 0;
}