質問L:キャンディ分け(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 3 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ツリーの層数+mを正解と記す

#include
#define maxn 100005
#define maxm 2000000
using namespace std;
struct node{
    int to;
    int next;
    int quan;
    int d;
}edge[maxm];
struct no{
    int u;
    int d;
};
int n, m, c, p, cnt;
int head[maxn], book[maxn];
void add(int u, int v, int w){
    edge[cnt].to = v;
    edge[cnt].quan = w;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
int main()
{
    int u, v, ans = 0;
    scanf("%d %d %d", &n, &p, &c);
    scanf("%d", &m);
    memset(head, -1, sizeof(head));
    for(int i = 1 ; i <= p ; ++ i){
        scanf("%d %d", &u, &v);
        add(u, v, m); add(v, u, m);
    }
    queue<no> que;
    no st;
    st.d = 1;
    st.u = c;
    que.push(st);
    while(!que.empty()){
        no t = que.front();
        que.pop();
        for(int i = head[t.u] ; i != -1 ; i = edge[i].next){
            int tt = edge[i].to;
            if(book[t.u] && book[tt]) continue;
            else{
                book[tt] = 1; book[t.u] = 1;
                ans = max(ans, t.d + 1);
                no temp;
                temp.d = t.d + 1; temp.u = tt;
                que.push(temp);
            }
        }


    }
    cout<<ans + m;
    return 0;
}

解法二:スタック最適化dijistra

#include
#define INF 0x3f3f3f3f
#define maxn 2000005
#define maxm 100005
using namespace std;
struct node{
    int to;
    int quan;
    int next;
}edge[maxn];
int n, m, sum, ans, cnt, p, c;
int head[maxm], book[maxm], dis[maxm];
int h[maxm], pos[maxm], siz;
void add(int u, int v, int w){
    edge[cnt].to = v;
    edge[cnt].quan = w;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
void init(){
    siz = n;
    for(int i = 1 ; i <= siz ; ++ i){
        pos[i] = i; h[i] = i;
    }
}
void siftdown(int i){
    int flag = 0, t;
    while(i * 2 <= siz && !flag){
        if(dis[h[i]] > dis[h[i * 2]])
            t = i * 2;
        else
            t = i;
        if(i * 2 + 1 <= siz){
            if(dis[h[i * 2 + 1]] < dis[h[t]])
                t = i * 2 + 1;
        }
        if(t != i){
            swap(h[t], h[i]);
            swap(pos[h[t]], pos[h[i]]);
            i = t;
        }
        else flag = 1;
    }
}
void siftup(int i){
    int flag = 0;
    if(i == 1) return;
    while(i != 1 && !flag){
        if(dis[h[i]] < dis[h[i / 2]]){
            swap(h[i], h[i / 2]);
            swap(pos[h[i]], pos[h[i / 2]]);
        }
        else flag = 1;
        i /= 2;
    }
}
void heap(){
    for(int i = siz / 2 ; i >= 1 ; i --){
        siftdown(i);
    }
}
int pop(){
    int t;
    t = h[1];
    pos[t] = 0;
    h[1] = h[siz];
    pos[h[1]] = 1;
    siz --;
    siftdown(1);
    return t;
}
void diji()
{
    //book[1] = 1;
    //sum ++;
    while( 1 ){
        int mini = INF, t = -1;
        t = pop();
        if(siz == 0) break;
        book[t] = 1;
        sum ++; //ans += dis[t];
        for(int i = head[t] ; i != -1 ; i = edge[i].next){
            int tt = edge[i].to;
            if(dis[tt] > dis[t] + edge[i].quan && !book[tt]){
                dis[tt] = dis[t] + edge[i].quan;
                ans = max(ans, dis[tt]);
                siftup(pos[tt]);
            }
        }
    }
}
int main()
{
    int u, v, w;
    memset(head, -1, sizeof(head));
    scanf("%d %d %d", &n, &p, &c);
    scanf("%d", &m);
    for(int i = 1 ; i <= n ; ++ i) dis[i] = INF;
    for(int i = 1 ; i <= p ; ++ i){
        scanf("%d %d", &u, &v);
        add(u, v, 1); add(v, u, 1);
    }
    /*for(int i = head[1] ; i != -1 ; i = edge[i].next){
        int tt = edge[i].to;
        dis[tt] = min(dis[tt], edge[i].quan);
    }*/
    dis[c] = 0;
    init();
    heap();
    diji();
    cout<<ans + m + 1;
    return 0;
}

解法三:spfa

#include
#define INF 0x3f3f3f3f
#define maxn 2000005
#define maxm 100005
using namespace std;
struct node{
    int to;
    int quan;
    int next;
}edge[maxn];
int n, m, sum, ans, cnt, p, c;
int head[maxm], book[maxm], dis[maxm];
void add(int u, int v, int w){
    edge[cnt].to = v;
    edge[cnt].quan = w;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
int main()
{
    int u, v, w;
    memset(head, -1, sizeof(head));
    scanf("%d %d %d", &n, &p, &c);
    scanf("%d", &m);
    for(int i = 1 ; i <= n ; ++ i) dis[i] = INF;
    for(int i = 1 ; i <= p ; ++ i){
        scanf("%d %d", &u, &v);
        add(u, v, 1); add(v, u, 1);
    }
    queue<int> que;
    dis[c] = 0;
    book[c] = 1;
    que.push(c);
    while(!que.empty()){
        int k = que.front();
        que.pop();
        for(int i = head[k] ; i != -1 ; i = edge[i].next){
            int tt = edge[i].to;
            if(dis[tt] > dis[k] + edge[i].quan){
                dis[tt] = dis[k] + edge[i].quan;
                ans = max(ans, dis[tt]);
                if(!book[tt]){
                    que.push(tt);
                    book[tt] = 1;
                }
            }
        }
        book[k] = 0;
    }
    cout<<ans + m + 1;
    return 0;
}