分糖果

题目描述

$n$ 个小朋友、 $p$ 条"彼此身旁"关系构成无权无向图。糖果第一秒从 $c$ 号出发，每秒沿一条边传给身旁还没糖的人；每人从拿到糖起再吃 $m$ 秒（边吃边发，不影响传播）。求全部吃完的时刻。输入第一行 $n, p, c$ ，第二行 $m$ ，接下来 $p$ 行每行一对身旁关系；输出一个数即答案。样例：输入 4 3 1 / 2 / 1 2 / 2 3 / 1 4 输出 5。数据范围： $1 \leqslant n \leqslant 100000$ ， $m \leqslant n(n-1)/2$ 。

思路

吃糖不影响传播：第 $v$ 个人在 $\text{dist}(v)+1$ 秒收到糖，再吃 $m$ 秒吃完。无权图单源最短路用 BFS 求，最后吃完的一定是离 $c$ 最远的人，故答案为 $\max(\text{dist}) + m + 1$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38# ROJ 1380 分糖果：从 C 出发的 BFS 最短路 + 吃糖时间
"""n 个小朋友、p 条无权边，C 开始发糖，每秒传一格、每个人收到后 m 秒吃完。
答案 = max(最短路) + m + 1。"""

import sys
from collections import deque


def main() -> None:
    data: list[str] = sys.stdin.buffer.read().split()
    it = iter(data)
    n, p, c = int(next(it)), int(next(it)), int(next(it))
    m = int(next(it))
    # 邻接表
    g: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(p):
        x, y = int(next(it)), int(next(it))
        g[x].append(y)
        g[y].append(x)

    # BFS 求 C 到所有人的最短路（每条边耗时 1 秒）
    INF = -1  # 用 -1 表示未访问
    dist: list[int] = [INF] * (n + 1)
    dist[c] = 0
    q = deque([c])
    while q:
        x = q.popleft()
        for y in g[x]:
            if dist[y] < 0:
                dist[y] = dist[x] + 1
                q.append(y)

    # 最晚收到糖的人：走了 max 秒，再花 m 秒吃完，且第一秒已经开始传
    print(max(dist[1:]) + m + 1)


if __name__ == "__main__":
    main()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:30
 * update_at: 2026-10-05 12:30
 */
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

int n, p, c, m;
vector<int> g[MAXN]; // g[i]：i 号小朋友身旁的人的编号列表
int dist[MAXN];      // dist[i]：糖从 C 传到 i 的最短时间（秒），-1 表示未访问

// 从 C 出发 BFS，求每个人最早拿到糖的时刻（每条边耗时 1 秒）
void bfs() {
    for (int i = 1; i <= n; i++) dist[i] = -1;
    dist[c] = 0;
    queue<int> q;
    q.push(c);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = 0; i < (int)g[x].size(); i++) {
            int y = g[x][i];
            if (dist[y] == -1) { // 每人只收一次糖
                dist[y] = dist[x] + 1;
                q.push(y);
            }
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &p, &c);
    scanf("%d", &m);
    for (int i = 1; i <= p; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }

    bfs();

    // 第 v 个人在 dist[v]+1 秒收到糖，再吃 m 秒吃完；
    // 最后吃完的一定是离 C 最远的人：ans = max(dist) + m + 1
    int max_dist = 0;
    for (int i = 1; i <= n; i++)
        if (dist[i] > max_dist) max_dist = dist[i];
    printf("%d\n", max_dist + m + 1);
    return 0;
}

目录

题目描述

思路

参考代码