分糖果

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

Input

Output

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;
}