C++实现糖果传递问题：计算所有小朋友吃完糖的时间

{"title": "C++实现糖果传递问题：计算所有小朋友吃完糖的时间", "description": "本题模拟了糖果在小朋友之间传递的过程，目标是计算出所有小朋友都吃完糖果所需的时间。使用C++语言，通过邻接表和BFS算法解决此问题，并提供详细的解题思路和代码实现。", "keywords": "糖果传递, BFS算法, 邻接表, C++, 图论, 最短距离", "content": "\u003cdiv class="entry-content"\u003e\u003ch2\u003e题目描述：\u003c/h2\u003e\u003cp\u003e童年的我们，将和朋友分享美好的事物作为自己的快乐。这天，C小朋友得到了Plenty of candies，将要把这些糖果分给要好的朋友们。已知糖果从一个人传给另一个人需要1 秒的时间，同一个小朋友不会重复接受糖果。由于糖果足够多，如果某时刻某小朋友接受了糖果，他会将糖果分成若干份，分给那些在他身旁且还没有得到糖果的小朋友们，而且自己会吃一些糖果。由于嘴馋，小朋友们等不及将糖果发完，会在得到糖果后边吃边发。每个小朋友从接受糖果到吃完糖果需要m秒的时间。那么，如果第一秒C小朋友开始发糖，第多少秒所有小朋友都吃完了糖呢? \u003c/p\u003e\u003cp\u003e\u003cstrong\u003e【输入】\u003c/strong\u003e\u003c/p\u003e\u003cp\u003e第一行为三个数n、p、c，为小朋友数、关系数和C小朋友的编号。\u003c/p\u003e\u003cp\u003e第二行为一个数m，表示小朋友吃糖的时间。\u003c/p\u003e\u003cp\u003e下面p行每行两个整数，表示某两个小朋友在彼此身旁。\u003c/p\u003e\u003cp\u003e\u003cstrong\u003e【输出】\u003c/strong\u003e\u003c/p\u003e\u003cp\u003e一个数，为所有小朋友都吃完了糖的时间。\u003c/p\u003e\u003ch2\u003e用C++语言解决内容：\u003c/h2\u003e\u003cpre\u003e\u003ccode\u003e#include\u003ciostream\u003e\n#include\u003cvector\u003e\n#include\u003cqueue\u003e\n#include\u003calgorithm\u003e\nusing namespace std;\n\nstruct Edge {\n int v, next;\n};\n\nconst int MAXN = 105;\nconst int MAXM = 1005;\n\nint n, p, c;\nint m;\nint head[MAXN], cnt;\nEdge edges[MAXM * 2];\nint dist[MAXN];\nbool vis[MAXN];\n\nvoid addEdge(int u, int v) {\n edges[cnt].v = v;\n edges[cnt].next = head[u];\n head[u] = cnt++;\n}\n\nvoid bfs(int u) {\n queue\u003cint\u003e q;\n q.push(u);\n dist[u] = 0;\n vis[u] = true;\n while (!q.empty()) {\n int cur = q.front();\n q.pop();\n for (int i = head[cur]; i != -1; i = edges[i].next) {\n int v = edges[i].v;\n if (!vis[v]) {\n dist[v] = dist[cur] + 1;\n vis[v] = true;\n q.push(v);\n }\n }\n }\n}\n\nint main() {\n cin \u003e\u003e n \u003e\u003e p \u003e\u003e c;\n cin \u003e\u003e m;\n for (int i = 1; i \u003c= n; i++) {\n head[i] = -1;\n dist[i] = -1;\n vis[i] = false;\n }\n cnt = 0;\n for (int i = 0; i \u003c p; i++) {\n int u, v;\n cin \u003e\u003e u \u003e\u003e v;\n addEdge(u, v);\n addEdge(v, u);\n }\n bfs(c);\n int maxDist = 0;\n for (int i = 1; i \u003c= n; i++) {\n maxDist = max(maxDist, dist[i]);\n }\n int ans = m * maxDist;\n cout \u003c\u003c ans \u003c\u003c endl;\n return 0;\n}\n\u003c/code\u003e\u003c/pre\u003e\u003ch2\u003e解题思路：\u003c/h2\u003e\u003cp\u003e首先使用邻接表构建图的数据结构，然后使用BFS算法计算出每个小朋友与C小朋友之间的最短距离。最后，将最短距离与吃糖的时间m相乘，即可得到所有小朋友都吃完糖的时间。\u003c/p\u003e\u003c/div\u003e