当前位置:网站首页>AcWing 1127. 香甜的黄油 题解(最短路—spfa)
AcWing 1127. 香甜的黄油 题解(最短路—spfa)
2022-07-02 18:27:00 【乔大先生】
AcWing 1127. 香甜的黄油
还是用spfa算法求最短路,思路就是找到每个牧场为中心点放置糖,找到所有奶牛移动距离和最小的牧场作为结果,输出移动和的最小值
#include<bits/stdc++.h>
using namespace std;
const int N = 810, M = 4000, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int d[N], q[N];
bool st[N];
int n, p, m;
int id[N]; //记录每个牧场的编号
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++ ;
}
int spfa(int start){
memset(d, 0x3f, sizeof d);
d[start] = 0;
int hh = 0, tt = 1;
q[0] = start;
st[start] = true;
while(hh != tt){
int t = q[hh ++ ];
if(hh == N) hh = 0;
st[t] = false;
for(int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if(d[j] > d[t] + w[i]){
d[j] = d[t] + w[i];
if(!st[j]){
q[tt ++ ] = j;
if(tt == N) tt = 0;
st[j] = true;
}
}
}
}
int res = 0;
for(int i = 0; i < n; i ++ ){
int j = id[i];
if(d[j] == INF) return INF;
res += d[j];
}
return res;
}
int main()
{
cin>>n>>p>>m;
for(int i = 0; i < n; i ++ ){
cin>>id[i];
}
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++ ){
int a, b, c;
cin>>a>>b>>c;
add(a, b, c);
add(b, a, c);
}
int minv = INF;
for(int i = 1; i <= p; i ++ ){
minv = min(minv, spfa(i));
}
cout<<minv<<endl;
return 0;
}
边栏推荐
- Quanzhi A33 uses mainline u-boot
- PHP asymmetric encryption method private key and public key encryption and decryption method
- Page title component
- 股票证券公司排名,有安全保障吗
- Getting started with typescript
- Use cheat engine to modify money, life and stars in Kingdom rush
- 新手必看,点击两个按钮切换至不同的内容
- golang:[]byte转string
- 线程应用实例
- 2022.7.1-----leetcode. two hundred and forty-one
猜你喜欢
Why should we build an enterprise fixed asset management system and how can enterprises strengthen fixed asset management
搭建主从模式集群redis
High frequency interview questions
全志A33使用主线U-Boot
PHP-Parser羽毛球预约小程序开发require线上系统
性能测试如何创造业务价值
数据降维——因子分析
高级性能测试系列《24. 通过jdbc执行sql脚本》
潇洒郎:彻底解决Markdown图片问题——无需上传图片——无需网络——转发给他人图片无缺失
教程篇(5.0) 10. 故障排除 * FortiEDR * Fortinet 網絡安全專家 NSE 5
随机推荐
Introduction of Ethernet PHY layer chip lan8720a
Page title component
metric_ Logger urination
"Patient's family, please come here" reading notes
PHP-Parser羽毛球预约小程序开发require线上系统
codeforces每日5题(均1700)-第四天
搭建主从模式集群redis
第七章-类基础
Progress progress bar
Introduction to the paper | application of machine learning in database cardinality estimation
PHP asymmetric encryption method private key and public key encryption and decryption method
The mybatieshelperpro tool can be generated to the corresponding project folder if necessary
4274. 后缀表达式-二叉表达式树
IDEA编辑器去掉sql语句背景颜色SQL语句警告No data sources are configured to run this SQL...和SQL Dialect is Not Config
End-to-End Object Detection with Transformers(DETR)论文阅读与理解
LeetCode 0871. Minimum refueling times - similar to poj2431 jungle adventure
Typescript 之 快速入门
Memory management of C
Use cheat engine to modify money, life and stars in Kingdom rush
Web2.0的巨头纷纷布局VC,Tiger DAO VC或成抵达Web3捷径