首页 > 编程语言 >南沙C++信奥赛陈老师解一本通题 1345:【例4-6】香甜的黄油

南沙C++信奥赛陈老师解一本通题 1345:【例4-6】香甜的黄油

时间:2024-10-31 12:20:35浏览次数:5  
标签:int 信奥赛 1345 牧场 通题 黄油 INF 奶牛 1001

 【题目描述】

农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1≤N≤500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。

农夫John很狡猾。像以前的巴甫洛夫,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声,以至他可以在晚上挤奶。

农夫John知道每只奶牛都在各自喜欢的牧场(一个牧场不一定只有一头牛)。给出各头牛在的牧场和牧场间的路线,找出使所有牛到达的路程和最短的牧场(他将把糖放在那)。

【输入】

第一行: 三个数:奶牛数N,牧场数P(2≤P≤800),牧场间道路数C(1≤C≤1450)。

第二行到第N+1行: 1到N头奶牛所在的牧场号。

第N+2行到第N+C+1行:每行有三个数:相连的牧场A、B,两牧场间距(1≤D≤255),当然,连接是双向的。

【输出】

一行 输出奶牛必须行走的最小的距离和。

【输入样例】

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

【输出样例】

8
#include <bits/stdc++.h>
using namespace std;
int g[1001][1001];
int d[1001][1001];
int a[1001];	//代表每个牧场有的奶牛数量 
#define INF 0x3f3f3f3f
void Floyd(int n)
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(d[i][j]>d[i][k]+d[k][j])
					d[i][j]=d[i][k]+d[k][j];
}
int main()
{
	int n,p,c,ans=INF,cow;
	cin>>n>>p>>c;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	memset(g,INF,sizeof(g));
	memset(d,INF,sizeof(d));
	for(int i=1;i<=c;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		g[x][y]=g[y][x]=w;
		d[x][y]=d[y][x]=w;
	}
	Floyd(p);
	for(int i=1;i<=p;i++)		//假设放在任何牧场编号i 
	{
		int total=0;
		for(int j=1;j<=n;j++)
			if(a[j]!=0 &&i!=a[j] ) 	//代表有路径  自己不需要路径  可以有多头牛,这里要多次运算 
				total+=d[ a[j] ][i];
		ans=min(ans,total);
	}
	cout<<ans;
	return 0;
}

 

标签:int,信奥赛,1345,牧场,通题,黄油,INF,奶牛,1001
From: https://www.cnblogs.com/nanshaquxinaosai/p/18517458

相关文章

  • 【信奥赛·算法基础】插入排序:算法解析与C++实现
    序言插入排序(InsertionSort)是一种简单的排序算法,就像是我们在打扑克牌时,整理手中牌的过程。一、基本原理插入排序的基本思想是:将待排序的元素插入到已经有序的部分序列中合适的位置,直到所有元素都插入完毕,整个序列就变为有序序列。二、算法步骤从第二个元素开始(假设第......
  • CSP/信奥赛C++刷题训练:经典二分例题(2):洛谷P1678:烦恼的高考志愿
    CSP/信奥赛C++刷题训练:经典二分例题(2)烦恼的高考志愿题目背景计算机竞赛小组的神牛V神终于结束了高考,然而作为班长的他还不能闲下来,班主任老t给了他一个艰巨的任务:帮同学找出最合理的大学填报方案。可是v神太忙了,身后还有一群小姑娘等着和他约会,于是他想到了同为计......
  • 【信奥赛·算法基础】CSP-J 枚举算法
    序言解决问题,并不是一开始就要找到最优解,而是在不断的调试中优化,将求解过程中耗时的部分、占用空间的部分尽可能的缩小,使得程序运行起来更高效一、定义与概念枚举算法,也叫穷举算法,是一种简单而直接的问题求解策略。它的核心思想是逐一列举问题的所有可能解,并逐一检验每个......
  • 【信奥赛·算法基础】CSP-J C++ 贪心算法示例汇总
    序言为了更清晰的了解贪心算法,我把常见的贪心算法示例做了一个总结,把问题和策略,以及代码示例放到了一起,方便学习和分析,这里示例仅以C++为例,其他语言可根据示例调整即可一、钱币找零问题问题描述:给定不同面额的钱币以及每种面额的数量,用最少的钱币张数凑齐给定的总金额。......
  • 【信奥赛·C++基础语法】CSP-J C++ STL 标准模板库 - 算法
    序言标准模板库(STL)的算法部分提供了一系列强大的工具,用于对各种容器中的数据进行操作。这些算法可以大大提高编程效率,减少代码重复,使程序更加简洁、高效和可读。无论是处理简单的数据结构还是复杂的大规模数据,STL算法都能发挥重要作用。一、STL算法的分类排序算法快速......
  • 南沙C++信奥赛陈老师解一本通题 1286:怪盗基德的滑翔翼
    ​【题目描述】怪盗基德是一个充满传奇色彩的怪盗,专门以珠宝为目标的超级盗窃犯。而他最为突出的地方,就是他每次都能逃脱中村警部的重重围堵,而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。有一天,怪盗基德像往常一样偷走了一颗珍贵的钻石,不料却被柯南小朋友识破了伪......
  • 【信奥赛·C++基础语法】CSP-J C++ 指针与引用
    序言指针和引用是非常重要的概念,它们提供了对内存的直接访问和操作方式,使得程序员能够更加灵活地处理数据哈,理解指针和引用的工作原理以及正确使用它们,对于编写高效、安全的C++程序至关重要。一、指针的基本概念指针的定义和作用指针是一个变量,它存储了另一个变量的内......
  • 南沙C++信奥赛陈老师解一本通题 1284:摘花生
    ​【题目描述】HelloKitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。HelloKitty只能向东或向南走,不能向西或......
  • 南沙C++信奥赛陈老师解一本通题 1943:【08NOIP普及组】排座椅
    ​ 【题目描述】上课的时候总有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的DD对同学上课时会交头接耳。同学们在教室中坐成了MM行NN列,坐在第ii行第jj列的同学的位置是(i,ji,j......
  • 南沙C++信奥赛陈老师解一本通题 1939:【07NOIP普及组】纪念品分组
    ​ 【题目描述】元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完......