哎呦的个人主页

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

网页索引

·【全新原创游戏！】新·超坑小游戏 官网
·【知识满满】那些让你崩溃的编程题：点我进入帖子列表
·【教程系列】教你手搓热门游戏-骗子酒馆：点击我进入
·【DIY一个属于自己的网站！】：点击我查看教程
·【图片仓库】：点击我进入

精彩推荐-那些让你崩溃的编程题

今天我们讨论的话题是———那些让你崩溃的编程题!
那么，我们要谈论的第一道题，就是洛谷的第P1828题：香甜的黄油~

P1828 香甜的黄油

题目描述

题目传送门
Farmer John 发现了做出全威斯康辛州最甜的黄油的方法：糖。
把糖放在一片牧场上，他知道 n 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。 奶牛：喂我花生……
Farmer John 很狡猾。像以前的 Pavlov，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。
Farmer John 知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

输入格式

第一行包含三个整数n,p,c，分别表示奶牛数、牧场数和牧场间道路数。
第二行到第n+1行，每行一个整数，其中第i行的整数表示第i−1头奶牛所在的牧场号。
第n+2行到第n+c+1行，每行包含三个整数A,B,D，表示牧场号为A和B的两个牧场之间有一条长度为D的双向道路相连。

输出格式

输出一行一个整数，表示奶牛必须行走的最小的距离和。

样例

输入：

3 4 5
2
3
4
1 2 1
1 3 1
2 3 7
2 4 3
3 4 5

输出：

8

说明/提示

对于所有数据，1≤n≤500，2≤p≤800，1≤A,B≤p，1≤c≤1450，1≤D≤255。

样例解释

          P2  
P1 @--1--@ C1
         |
         | 
       5  7  3
         |   
         |     C3
       C2 @--5--@
          P3    P4

把糖果放在4号牧场最优。

题目分析+做题过程

一开始哎呦还以为这就是一个简单的最短路问题，结果后面直接给整崩溃了……
因为哎呦最新学习了SPFA最短路，所以哎呦干脆就直接套用模板写了一段代码：

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
该如何解决这个问题呢？哎呦苦苦思索了两周，终于想到一个办法：
找一个大冤种同学借鉴答案！
于是，哎呦打开提交记录，随便找了一个同学的答案借鉴起来：
l1
广告推销：该同学建造的网站：piaoztsdy’s blog
经过深入研究，哎呦终于得出了答案：
这个暴力不仅容易超时，在循环的时候居然连起点和终点都搞错了啊……
简单描述一下代码的“高”效率：
·原本只需要对每一个i跑1次SPFA（以i为起点），但哎呦当时可能一时激动，
亿不小心就把O(pc)的时间复杂度飙到了O(npc)（你确定这个复杂度是认真的？）
还有，哎呦一开始定义数组的时候写了这么一段代码：

int dis[810],vis[2910]; //重点在这一行代码上
int head[810],to[2920],nxt[2920],w[2920],at[2920]; //用来链表建边的数组

已知一共只会有不到800个点的情况下，
哎呦居然把vis数组直接开到了将近3000多……我说这不是我写的代码你信吗？
终于，耗尽将近3周努力，哎呦写出了第一份修改版代码：

for(int i = 1;i <= p;i++){ //枚举放置糖果的位置
    spfa(i); //以i为起点，计算i到所有牧场的最短路
    int cnt = 0;
    for(int j = 1;j <= n;j++){
        cnt += dis[at[j]]; //记录i到奶牛所在牧场at[j]的距离
    }
    if(cnt < ret) ret = cnt; //取最小值成为答案
}

哎呦用颤抖的手按下了“提交代码”按钮，然后……
一秒，两秒，三秒……
check
成功了！
哎呦已经猜到，很多小盆友正迫不及待地要答案……
哎呦只有一句话：不可能！绝对不可能！
虽然这道题对很多大佬来说只是一个简单的水题，没什么好说的……
但哎呦还是很感谢能坚持到现在的你们……
这篇帖子到这里就结束了，如果想查看更多帖子，可以前往网页索引查看。
我们下一个系列不见不散！

帖子信息

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