当前位置:网站首页>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;
}
边栏推荐
- QT中的QPropertyAnimation使用和toast案列
- Npoi export Excel2007
- 搭建主从模式集群redis
- 数字滚动带动画
- A4988 drive stepper motor "recommended collection"
- 性能测试如何创造业务价值
- Develop fixed asset management system, what voice is used to develop fixed asset management system
- Why should we build an enterprise fixed asset management system and how can enterprises strengthen fixed asset management
- 虚拟机初始化脚本, 虚拟机相互免秘钥
- What is the MySQL backup suffix_ MySQL backup restore
猜你喜欢
Markdown基础语法
ICDE 2023|TKDE Poster Session(CFP)
Quanzhi A33 uses mainline u-boot
仿京东放大镜效果(pink老师版)
Hospital online inquiry source code hospital video inquiry source code hospital applet source code
教程篇(5.0) 09. RESTful API * FortiEDR * Fortinet 网络安全专家 NSE 5
[error record] problems related to the installation of the shuttle environment (follow-up error handling after executing the shuttle doctor command)
Yunna | why use the fixed asset management system and how to enable it
What is 9D movie like? (+ common sense of dimension space)
Excel finds the same value in a column, deletes the row or replaces it with a blank value
随机推荐
[test development] takes you to know what software testing is
教程篇(5.0) 09. RESTful API * FortiEDR * Fortinet 网络安全专家 NSE 5
冒泡排序数组
Notes de lecture sur le code propre
ICDE 2023|TKDE Poster Session(CFP)
4274. Suffix expression - binary expression tree
Date tool class (updated from time to time)
How to print mybats log plug-in using XML file
Typescript 之 快速入门
【pytorch学习笔记】Tensor
GMapping代码解析[通俗易懂]
How performance testing creates business value
Reading notes of code neatness
Emmet基础语法
450-深信服面经1
程序猿入门攻略(十二)——数据的存储
xml开发方式下AutowiredAnnotationBeanPostProcessor的注册时机
线程应用实例
Web2.0 giants have deployed VC, and tiger Dao VC may become a shortcut to Web3
Advanced performance test series "24. Execute SQL script through JDBC"