当前位置:网站首页>【最短路】ACwing 1127. 香甜的黄油(堆优化的dijsktra或spfa)
【最短路】ACwing 1127. 香甜的黄油(堆优化的dijsktra或spfa)
2022-07-07 09:46:00 【暮色_年华】
抽象问题:
求所有奶牛到某个点的最短距离和的最小值。
由于是双向的,可以看成从某个点到所有其他点的最短距离的最小值。
所以,可以看成是单源最短路问题,由于是稀疏图且没有负边,所以可以使用堆优化的dij或者spfa
import java.io.*;
import java.util.*;
class Main{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static final int N=10000;
static final int INF=(int)1e8;
static int[]dist=new int[N];
static int[]h=new int[N];
static int[]ne=new int[N];
static int[]e=new int[N];
static int[]w=new int[N];
static int[]nums=new int[N];
static boolean[] st=new boolean[N];
static int idx;
static int n,p,c;
public static void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
public static void dijskra(int start){
PriorityQueue<int[]>pq=new PriorityQueue<>(p,(a,b)->a[1]-b[1]);
Arrays.fill(dist,INF);
Arrays.fill(st,false);
dist[start]=0;
pq.add(new int[]{start,0});
while(!pq.isEmpty()){
int[]cur=pq.poll();
int v=cur[0];
int d=cur[1];
if(st[v])continue;
st[v]=true;
for(int i=h[v];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>d+w[i]){
dist[j]=d+w[i];
pq.add(new int[]{j,dist[j]});
}
}
}
}
public static void main(String[] args)throws IOException{
String[] s=br.readLine().split(" ");
n=Integer.parseInt(s[0]);
p=Integer.parseInt(s[1]);
c=Integer.parseInt(s[2]);
for(int i=1;i<=n;i++){
int t=Integer.parseInt(br.readLine());
nums[t]++;
}
Arrays.fill(h,-1);
for(int i=0;i<c;i++){
s=br.readLine().split(" ");
int a=Integer.parseInt(s[0]);
int b=Integer.parseInt(s[1]);
int c=Integer.parseInt(s[2]);
add(a,b,c);
add(b,a,c);
}
int res=INF;
for(int i=1;i<=p;i++){
dijskra(i);
int sum=0;
for(int j=1;j<=p;j++){
sum+=dist[j]*nums[j];
}
res=Math.min(res,sum);
}
System.out.println(res);
}
}
spfa:
import java.io.*;
import java.util.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static final int N=5000;
static final int INF=(int)1e8;
static int[]h=new int[N];
static int[]ne=new int[N];
static int[]e=new int[N];
static int[]w=new int[N];
static int[]dist=new int[N];
static boolean[]st=new boolean[N];
static int idx;
static int[]nums=new int[N];
static int n,p,c;
public static void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
public static void spfa(int start){
Arrays.fill(dist,INF);
dist[start]=0;
Queue<Integer>q=new LinkedList<>();
q.add(start);
st[start]=true;
while(!q.isEmpty()){
int cur=q.poll();
st[cur]=false;
for(int i=h[cur];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[cur]+w[i]){
dist[j]=dist[cur]+w[i];
if(!st[j]){
q.add(j);
st[j]=true;
}
}
}
}
}
public static void main(String[]args)throws IOException{
String[]s=br.readLine().split(" ");
n=Integer.parseInt(s[0]);
p=Integer.parseInt(s[1]);
c=Integer.parseInt(s[2]);
for(int i=1;i<=n;i++){
int t=Integer.parseInt(br.readLine());
nums[t]++;
}
Arrays.fill(h,-1);
for(int i=0;i<c;i++){
s=br.readLine().split(" ");
int a=Integer.parseInt(s[0]);
int b=Integer.parseInt(s[1]);
int w=Integer.parseInt(s[2]);
add(a,b,w);
add(b,a,w);
}
int res=INF;
for(int i=1;i<=p;i++){
spfa(i);
int sum=0;
for(int j=1;j<=p;j++){
sum+=dist[j]*nums[j];
}
res=Math.min(res,sum);
}
System.out.println(res);
}
}
边栏推荐
- JS add spaces to the string
- sink 消费 到 MySQL, 数据库表里面已经设置了 自增主键, flink 里面,如何 操作?
- electron添加SQLite数据库
- Audit migration
- The database synchronization tool dbsync adds support for mongodb and es
- Easyui学习整理笔记
- 使用MeterSphere让你的测试工作持续高效
- 聊聊SOC启动(十一) 内核初始化
- Le Cluster kubernets en cours d'exécution veut ajuster l'adresse du segment réseau du pod
- Verilog realizes nixie tube display driver [with source code]
猜你喜欢
Avoid mutating a prop directly since the value will be overwritten whenever the parent component
数据库同步工具 DBSync 新增对MongoDB、ES的支持
Activity生命周期
Talk about SOC startup (x) kernel startup pilot knowledge
[system design] index monitoring and alarm system
测试开发基础,教你做一个完整功能的Web平台之环境准备
Use metersphere to keep your testing work efficient
What if copying is prohibited?
Antd select selector drop-down box follows the scroll bar to scroll through the solution
90后,辞职创业,说要卷死云数据库
随机推荐
How to remove addition and subtraction from inputnumber input box
The database synchronization tool dbsync adds support for mongodb and es
How to add aplayer music player in blog
對比學習之 Unsupervised Learning of Visual Features by Contrasting Cluster Assignments
毕业季|与青春作伴,一起向未来!
STM32 entry development write DS18B20 temperature sensor driver (read ambient temperature, support cascade)
Qt|多个窗口共有一个提示框类
There are so many factors that imprison you
竟然有一半的人不知道 for 与 foreach 的区别???
Design intelligent weighing system based on Huawei cloud IOT (STM32)
关于SIoU《SIoU Loss: More Powerful Learning for Bounding Box Regression Zhora Gevorgyan 》的一些看法及代码实现
. Net Maui performance improvement
Array object sorting
What is high cohesion and low coupling?
Test the foundation of development, and teach you to prepare for a fully functional web platform environment
Some opinions and code implementation of Siou loss: more powerful learning for bounding box regression zhora gevorgyan
The annual salary of general test is 15W, and the annual salary of test and development is 30w+. What is the difference between the two?
技术分享 | 抓包分析 TCP 协议
Talk about SOC startup (IX) adding a new board to uboot
深度学习秋招面试题集锦(一)