哎呦的个人主页

初次见面，欢迎来到编程小白哎呦的个人主页！
这个网页的内容可能会随时改动，主要分享的是哎呦的一些日常
如果发现网站内容丢失请不要见怪^__^以下是网页索引，
大家可以点击链接观看想看的帖子~

网页索引

·【全新原创游戏！】新·超坑小游戏 官网
·【知识满满】那些让你崩溃的编程题：点我进入帖子列表
·【教程系列】各种冷门的C++小妙招：点击我进入

商业推销

【快捷链接】

把糖果放在4号牧场最优。
### 题目分析+做题过程
一开始哎呦还以为这就是一个简单的**最短路**问题，结果后面直接给整~~崩溃~~了……  
因为哎呦最新学习了SPFA最短路，所以哎呦干脆就**直接套用模板**写了一段代码：  
```cpp
void spfa(int u){
	for(int i = 1;i <= p;i++){ //初始化dis数组
		dis[i] = inf;
	}
	memset(vis,0,sizeof(vis));
	vis[u] = 1;
	dis[u] = 0;
	q.push(u);
	while(!q.empty()){
		int f = q.front(); q.pop(); //从队列中取出一项
		vis[f] = 0;
		//利用这个元素更新其他元素的最短路
		for(int i = head[f];i != -1;i = nxt[i]){
			int v = to[i]; //取出一个元素
			if(dis[f] + w[i] < dis[v]){ //找到了更短的路径
				dis[v] = dis[f] + w[i]; //更新最短路
				if(vis[v] == 0){
					q.push(v); //入队
					vis[v] = 1; //标记，防止重复入队
				}
			}
		}
	}
}

（建边和输入代码肯定是有的，这里为了省空间，只放出来一部分）
ps：代码的大致意思在注释里，实在想看完整解释的可以直接上网搜索
这题的最短路部分并不是很复杂（毕竟也算是模板题），唯一让哎呦感到恶心的是如何选择放置糖果的位置
看着身边的同学都胸有成竹地敲起了代码，哎呦几乎快要当场晕厥了
这时，哎呦灵光一现，俗话都说暴力就是真神（你确定不是自己编的？），
既然题目要求选择一个牧场作为最短路的终点，那我直接用一个数组记录每个牧场的位置，
再暴力枚举简单搞搞，不就可以check这道题了吗？
因为题目要求一共有p只牛，所以哎呦简单写了一个自己都不知道什么意思的循环……

for(int i = 1;i <= p;i++){
          int cnt = 0;
          for(int j = 1;j <= n;j++){
                    spfa(at[j]);
                    cnt += dis[i];
	}
	if(cnt < ret) ret = cnt;
}

然后，果不其然……
img1
该如何解决这个问题呢？哎呦苦苦思索了两周，终于想到一个办法……
欲知后事如何？快到《那些让你崩溃的编程题》中寻找答案吧！

帖子信息

最新版本：2025-12-18-20:00
最新更新时间：2025年12月20日21时