分糖果(candy)（信息学奥赛一本通- P1380）
【题目描述】
童年的我们，将和朋友分享美好的事物作为自己的快乐。这天，C小朋友得到了Plenty of candies，将要把这些糖果分给要好的朋友们。已知糖果从一个人传给另一个人需要1 秒的时间，同一个小朋友不会重复接受糖果。由于糖果足够多，如果某时刻某小朋友接受了糖果，他会将糖果分成若干份，分给那些在他身旁且还没有得到糖果的小朋友们，而且自己会吃一些糖果。由于嘴馋，小朋友们等不及将糖果发完，会在得到糖果后边吃边发。每个小朋友从接受糖果到吃完糖果需要m秒的时间。那么，如果第一秒C小朋友开始发糖，第多少秒所有小朋友都吃完了糖呢?
【输入】
第一行为三个数n、p、c，为小朋友数、关系数和C小朋友的编号。
第二行为一个数m，表示小朋友吃糖的时间。
下面p行每行两个整数，表示某两个小朋友在彼此身旁。
【输出】
一个数，为所有小朋友都吃完了糖的时间。
【输入样例】
4 3 1 2 1 2 2 3 1 4【输出样例】
5【提示】
【样例解释】
第一秒，糖在1手上。第二秒，糖传到了2、3的手中。第三秒，糖传到了4的手中，此时1吃完了。第四秒，2、3吃完了。第五秒，4吃完了。所以答案是5。
【限制】
40%的数据满足：1≤n≤100;
60%的数据满足：1≤n≤1000;
100%的数据满足：1≤n≤100000;
m≤n×(n−1)2,不会有同一个关系被描述多次的情况。
0. 题目概要
有N个小朋友（N<=100,000）和P条好友关系。糖果从起点C开始传递，每一秒传给相邻的朋友。每个人吃糖需要m秒。
求：所有人都吃完糖果的时刻。
核心转化：
所有人吃完的时刻 = max(每个人拿到糖的时刻+m)。
问题转化为：求起点C到其他所有点的最短路径（距离即为时间）。
1. 算法选型
题目中传递时间固定为 1 秒，即所有边权均为 1。
BFS：无权图最优解，复杂度O(N+P)。
Dijkstra (邻接表+堆优化)：通用性强，复杂度O(P log N)，本题解采用此方法作为模板练习。
2. 深度解析：为什么不能开 100 亿数组？
这是本题最大的思维陷阱。有同学看到N=10^5，第一反应是：“边数上限M最多可能是完全图 N^2 = 10^10 吗？”
于是反手开了一个 long long vtex[10000000000] —— 虽然这道题没问题，但别的编译器可能将直接导致 MLE或者 CE。
这里要讲一个信奥赛场上的“数据规模跷跷板定律”：
2.1 内存与时间的物理极限
如果真的有10^10条边：
内存：10^10*4B *3(数组)约等于120GB。普通比赛限制仅 256MB，根本存不下。
时间：光是
cin读取100亿个数，就需要好几个小时，而比赛时限通常只有1秒。
2.2 出题人的平衡
在算法题中，N（点）和 M（边）永远是动态平衡的：
情形 A：稠密图 (M约等于N^2)
出题人为了不超时，一定会把N限制得很小（通常N<=2000）。
此时才需要考虑邻接矩阵。
情形 B：稀疏图 (M与N同量级)
当N达到10^5级别时，出题人必须限制M的大小，通常M只会是N的几倍或几十倍（如2*10^5或 50 *10^5）。
2.3 为什么开100*maxn？
常规开
2*maxn导致tle，说明测试数据中边数不少（半稠密图）。为了防止数组越界，我们直接开到
100*maxn（约 1000 万容量）。
2.4 为什么没炸内存？
理论计算：1000 万的
int数组*3约等于114MB>64MB。实际情况：利用操作系统的按需分配机制。只要
idx指针没有真正推到 1000 万，未使用的数组空间就不会占用物理内存。结果：既防住了边数过多的RE（本题还会造成TLE），又利用系统特性躲过了 MLE。
结论：
看到N=10^5，不要害怕N^2的边数。边数组 (vtex, nxt, wt) 开到 5000000 到 10000000 基本上足够且安全。
3. 完整代码
//点数10^5量级 用Dijkstra #include <iostream> #include <cstring> #include <queue> using namespace std; int n,p,c,m; const int maxn=100010; int h[maxn]; int vtex[100*maxn]; int nxt[100*maxn]; int wt[100*maxn]; int vis[maxn]; int dis[maxn]; int idx; struct node{ int id;//小朋友编号 int w;//到c小朋友的距离 //优先队列默认大根堆，重载运算符修改为小根堆 friend bool operator <(node a,node b){ return a.w>b.w; } }; priority_queue<node> q; void dijkstra(int s){ dis[s]=1;//这个不能丢 node tmp; tmp.id=s; tmp.w=1;//第一秒，糖在1手上，起始就是1秒 q.push(tmp);//起点入队 while(!q.empty()){ tmp=q.top(); q.pop(); int nid=tmp.id; if(vis[nid]==1) continue;//如果tmp已经出队过，就跳过 vis[nid]=1;//如果没有出队过，就打上标记 int p=h[nid]; while(p!=-1){ if(vis[vtex[p]]==0){ if(dis[vtex[p]]>dis[nid]+wt[p]){ dis[vtex[p]]=dis[nid]+wt[p]; q.push({vtex[p],dis[vtex[p]]}); } } p=nxt[p]; } } } void addedge(int u,int v,int w){ vtex[idx]=v; nxt[idx]=h[u]; wt[idx]=w; h[u]=idx++; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>p>>c;//小朋友数 关系数（边数） 起点 cin>>m;//吃糖时间 memset(h,-1,sizeof(h));//初始化头指针数组 //邻接表存图 for(int i=1;i<=p;i++){ int u,v,w; cin>>u>>v; w=1;//小朋友传给小朋友需要1s addedge(u,v,w);//双向的 addedge(v,u,w); } for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;//初始化每个小朋友到c小朋友距离为无穷 dijkstra(c); int ma=0; for(int i=1;i<=n;i++){//遍历所有朋友，找最长时间 if(dis[i]!=0x3f3f3f3f) ma=max(ma,dis[i]); } cout<<ma+m;//输出最长传递时间+那个人吃糖果时间 return 0; }