1380:キャンディ(candy)

【タイトル説明】
子供の頃の私たちは、友达と素晴らしいことを自分の楽しみとして分かち合います.この日、CさんはPlenty of candiesをもらい、これらのキャンディを親友たちに分けます.キャンディがある人から別の人に伝わるのに1秒かかることが知られており、同じ子供がキャンディを繰り返し受け取ることはありません.キャンディは十分に多いので、ある时ある子供がキャンディを受け取ったら、彼はキャンディをいくつかに分けて、彼のそばにいてまだキャンディを手に入れていない子供たちに分けて、自分でキャンディを食べます.食いしん坊なので、子供たちはキャンディを出すのが待ちきれず、キャンディを手に入れた後、食べながら出します.子供一人一人がキャンディを受け取るからキャンディを食べ終わるまでm秒かかります.では、最初の秒Cの子供が砂糖を出し始めたら、何秒目にすべての子供が砂糖を食べ終わったのでしょうか.
【入力】
第1の行為の3つの数n、p、cは、子供数、関係数、C子供の番号である.
第2の行為は1つの数mで、子供が砂糖を食べる時間を表しています.
次のp行は行ごとに2つの整数で、ある2人の子供がお互いのそばにいることを示しています.
【出力】
1つの数で、すべての子供のために砂糖を食べ終わった時間です.
【入力サンプル】

4 3 1
2
1 2
2 3
1 4

【出力サンプル】

5

【ヒント】
【様式解釈】
1秒目、砂糖は1手にあります.2秒目、砂糖が2、3の手に伝わった.3秒目、砂糖は4の手に伝わり、この時1は食べ終わった.4秒目、2、3は食べ終わった.5秒目、4が食べ終わった.だから答えは5です.
【制限】
40%のデータ満足:1≦n≦100
60%のデータ満足:1≦n≦1000
100%のデータ満足:1≦n≦100000
m≦n*(n−1)/2であり、同じ関係が複数回記述されることはない.
 
この問題は最短経路でできるが、実はこの問題は木の深さを求めるので、bfsを使ってもいい.bfsは過ぎたが、dfsは過ぎていない.なぜか分からない.
最短絡的な考え方で4-1-2-3この図は1から1の重み値が1で最後に求めた1から別の点の最大値が2で1までの時間を加え、最後に食べ終わる時間が5少ないことを説明します.

#include
using namespace std;
const int inf=0x3f3f3f3f;
const int N=100100;
int dis[N*10];
struct node
{
    int from;
    int to;
    int next;
    int dis;
}s[N*20];
int head[N*10]={0};
int vis[N]={0};
int cnt=0;
void add_edge(int from,int to,int dis)
{
    s[++cnt].next=head[from];
    s[cnt].to=to;
    s[cnt].dis=dis;
    head[from]=cnt;
}
int n,p,c;
int m;

void spfa(int ss)
{
    memset(dis,inf,sizeof(dis));

    vis[ss]=1;
    dis[ss]=0;
    queueQ;
    Q.push(ss);
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        vis[u]=0;
        for(int i=head[u];i!=0;i=s[i].next){
            int to=s[i].to;
            int di=s[i].dis;
            if(dis[to]>dis[u]+di){
                dis[to]=dis[u]+di;
                if(!vis[to]){
                    vis[to]=1;
                    Q.push(to);
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>p>>c>>m;
    memset(head,0,sizeof(head));
    for(int i=0;i
>x>>y;
        add_edge(x,y,1);
        add_edge(y,x,1);
    }
    spfa(c);
    int maxn=-1;
    for(int i=1;i<=n;i++){
        if(maxn

 
 
bfsを使うのは木の深さを捜索するので、どれだけ高くて、bfs AC、どうしてDFSがACがないのが0分感じますこのウェブサイトは时にはデータをテストして本当に问题があります
 
bfsを使う時ansを求める時forの中で+1が最大値を求めるので、外では必要ありません.これは最後の1つがforに入ることができないため、外でプラスしなくてもいいです.

#include
#include
#include
#include
using namespace std;
int n,p,c,m;
vectorg[100005];
int vis[100005];

struct node
{
    int to;
    int step;
    node(){}
    node(int to1,int step1):to(to1),step(step1){}
};

int ans;

void bfs(int to)
{
    vis[to]=1;
    queueQ;
    Q.push(node(to,1));
    while(!Q.empty()){
        node u=Q.front();
        Q.pop();
        //ans=u.step;
        for(int i=0;i

 
 
dfs 0点、これはあり得なくて、少しも点がないことはあり得なくて、だからウェブサイトは問題があるかもしれません

#include
#include
#include
#include
#include
using namespace std;
int n,p,c,m;
vectorg[100005];
int vis[100005];


int ans=-1;
int viss[100005];
void dfs(int to,int step)
{
    if(step<=ans) return;
    ans=max(ans,step);


    for(int i=0;i