Hello everyone , I meet you again , I'm the king of the whole stack .

Divide candy

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

In childhood, we will share good things with our friends as our own happiness . On the day ,C The children got candy , I'm going to give these sweets to my best friends . It is known that candy is passed from one person to another who needs 1 The second time , The same child will not accept candy repeatedly . Because there are enough sweets , Suppose a child accepts candy at some time . He will divide the candy into several parts , Give it to the children who are beside him and haven't got candy yet , And I will eat some candy . Because of greediness , The children can't wait to send out the candy , Will eat and distribute after getting candy . Every child needs... From accepting candy to eating it m The second time . that , Suppose the first second C The children began to send sugar , In a few seconds, all the children finished eating sugar ？

Input

Input has multiple sets of data , The data of each group is no 1 Act three numbers n(<=10000),p(<=600000),c Count the children , Relationship number and C Number... Children . The first 2 Behavior a number m(<=8000), It means the time for children to eat sugar . following p Two integers per line , It means that two children are beside each other .

Output

For each set of inputs, output a separate integer representation from Ts To Te The minimum total cost of . Data guarantees that there is at least one path .

Sample Input

4 3 1
2
1 2
2 3
1 4

Copy

Sample Output

5

Hint
 The first second , Sugar in 1 On hand . The second seconds , The sugar reached 2、4 In the hands of . The third second . The sugar reached 3 In the hands of , here 1 I'm full . The fourth second ,2、4 I'm full . The fifth second .3 I'm full . So the answer is 5.

Copy

Author

HYNU

// The idea is to find out and 1 From the farthest point to 1 Distance of , First, mark the weight of each path as 1. Find the farthest point and add m That's the answer. . Because the last person to eat sugar needs m Time , Suppose this person has finished eating in the end , Then the person in front of him must have finished . When searching, we use the breadth first search of graph , because n A very large . So use vector Dynamic array to store edges .

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

Copy

Copyright notice ： This article is the original article of the blogger . Blog , Do not reprint without permission .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/117097.html Link to the original text ：https://javaforall.cn