acwing1127. 香甜的黄油

2023-10-23 17:51
文章标签 黄油 香甜 acwing1127

本文主要是介绍acwing1127. 香甜的黄油,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意

在这里插入图片描述

思路

暴力 spfa。。。。。

代码

#include <bits/stdc++.h>
using namespace std;
#define db  double
#define ll  long long
#define Pir pair<int, int>
#define fi  first
#define se  second
#define pb  push_back
#define m_p make_pair
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
/*==========ACMer===========*/
const int N = 805, M = 3000;
int n, p, c;
int a[N];
struct Edge
{int v, w, ne;
} e[M];
int h[N], tot;
void add(int u, int v, int w)
{e[++ tot] = { v, w, h[u] }; h[u] = tot;
}int dis[N], vis[N];void spfa(int s)
{memset(dis, inf, sizeof dis);dis[s] = 0, vis[s] = 1;queue<int> q;q.push(s);while (q.size()){int u = q.front(); q.pop();vis[u] = 0;for (int i = h[u]; i; i = e[i].ne) {int v = e[i].v, w = e[i].w;if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;if (! vis[v]){vis[v] = 1;q.push(v);}}}}
}int main()
{scanf("%d %d %d", &n, &p, &c);for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);int u, v, w;for (int i = 0; i < c; i ++) {scanf("%d %d %d", &u, &v, &w);add(u, v, w);add(v, u, w);}ll ans = inf;for (int i = 1; i <= p; i ++) {spfa(i);ll sum = 0;for (int j = 1; j <= n; j ++) {sum += dis[a[j]];}ans = min(ans, sum);}printf("%lld\n", ans);return 0;
}

这篇关于acwing1127. 香甜的黄油的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/269469

相关文章

算法提高之香甜的黄油

算法提高之香甜的黄油 核心思想:spfa 遍历所有点作为起点 spfa求最短路最后求和返回 求最小 #include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 810,M = 3000,INF = 0x3f3f3f3f;int n,p,m;int id[N];int

3月黄油奶酪行业数据分析:安佳和妙可蓝多领军市场

近些年来,随着新消费主义盛行,老少皆宜的黄油和奶酪逐渐成为都市年轻人的烘培“新宠”。 今年3月份,黄油奶酪表现的中规中矩,处在稳定发展阶段。根据鲸参谋数据显示,3月份,在线上综合电商平台(京东天猫淘宝)上黄油奶酪共卖出了将近360万件,环比上个月上涨了45%;销售额累计约1.5亿元,环比上个月上涨32%。 *数据源于鲸参谋(来自公开渠道获取与统计,数据仅供参考) 观察黄油奶酪产品的价

#堆优化dijkstra#洛谷 1828 jzoj 1287 codevs 2038 ssl 1693 香甜的黄油

题目 有 n n n个点,求每个点的单源最短路径的最短和 分析 其实跑 n n n遍 s p f a spfa spfa或 d i j k s t r a dijkstra dijkstra堆优化就行了 代码 #include <cstdio>#include <queue>struct node{int y,w,next;}e[2901];int n,m,dis[801]

珂朵莉与黄油面包 SDUT

珂朵莉与黄油面包 SDUT Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description 珂朵莉非常喜欢吃黄油面包,现在珂朵莉想吃一个大小为 d 的黄油面包,你能满足她么? Input 一个正整数 d 。(1<= d <=20) Output 一个高和宽均为 2*d-1 的图形,代表一个

P1828 [USACO3.2]香甜的黄油 Sweet Butter

快速链接 原题链接题目大意输入格式输出格式数据范围解题思路上代码 原题链接 P1828 题目类型: 普 及 + / 提 高 {\color{green}{普及+/提高}} 普及+/提高 AC记录:Accepted 题目大意 有 n n n头牛在不同的牧场,牧场之间有路线和路线的长度。现在让你找出一个牧场 k k k,使得奶牛们到牧场 k k k的总长度最短。 输入格式

[spfa]香甜的黄油

题目描述 农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。   农夫John很狡猾。像以前的Pavlov,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声,以至他可以在晚上挤奶。   农夫John知道每只

【SSL_P1693/洛谷P1828】香甜的黄油 Sweet Butter

香甜的黄油 Sweet Butter 题目链接:香甜的黄油 Sweet Butter 题目描述 农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。 农夫John很狡猾。像以前的Pavlov,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场

2024年1月12日:清爽无糖rio留下唇齿之间的香甜

友利奈绪的时间管理 2024年1月12日08:02:28进行java程序设计的上课准备 2024年1月12日08:02:44知道java的题目有18道 2024年1月12日08:43:07随机数去重比较 2024年1月12日08:54:03C语言题目最小公倍数 2024年1月12日08:58:37C语言题目二维数组变一维数组 2024年1月12日10:03:20数据结构森林转化为二叉树

例4.6 香甜的黄油(butter)

我的个人博客:个人博客 转载于信息学奥赛一本通 【题目描述】 农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1≤N≤500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。 农夫John很狡猾。像以前的巴甫洛夫,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声,

[Usaco-3.2.6] Sweet Butter香甜的黄油

usaco-3.2.6 Sweet Butter香甜的黄油 时间限制: 1 Sec 内存限制: 128 MB 题目描述 农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。 农夫John很狡猾。像以前的Pavlov,他知道他可以训练这些奶牛,让它们在听到