当前位置:网站首页>[shortest circuit] acwing 1127 Sweet butter (heap optimized dijsktra or SPFA)
[shortest circuit] acwing 1127 Sweet butter (heap optimized dijsktra or SPFA)
2022-07-07 11:46:00 【Twilight_ years】
Abstract problem :
Find the minimum value of the sum of the shortest distances of all cows to a certain point .
Because it's two-way , It can be regarded as the minimum value of the shortest distance from a certain point to all other points .
therefore , It can be regarded as the single source shortest path problem , Because it is a sparse graph and has no negative edges , So you can use heap optimized dij perhaps 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);
}
}
边栏推荐
- Software design - "high cohesion and low coupling"
- 使用MeterSphere让你的测试工作持续高效
- 禁锢自己的因素,原来有这么多
- OneDNS助力高校行业网络安全
- [encapsulation of time format tool functions]
- EasyUI learn to organize notes
- SwiftUI Swift 内功之如何在 Swift 中进行自动三角函数计算
- Reasons for the failure of web side automation test
- 【神经网络】卷积神经网络CNN【含Matlab源码 1932期】
- R language uses image of magick package_ Mosaic functions and images_ The flatten function stacks multiple pictures together to form a stack layers on top of each other
猜你喜欢
How to add aplayer music player in blog
SwiftUI 4 新功能之掌握 WeatherKit 和 Swift Charts
聊聊SOC启动(十一) 内核初始化
Onedns helps college industry network security
总结了200道经典的机器学习面试题(附参考答案)
La voie du succès de la R & D des entreprises Internet à l’échelle des milliers de personnes
How much do you know about excel formula?
The road to success in R & D efficiency of 1000 person Internet companies
千人規模互聯網公司研發效能成功之路
CMU15445 (Fall 2019) 之 Project#2 - Hash Table 详解
随机推荐
Verilog realizes nixie tube display driver [with source code]
浙江大学周亚金:“又破又立”的顶尖安全学者,好奇心驱动的行动派
Table replication in PostgreSQL
CMU15445 (Fall 2019) 之 Project#2 - Hash Table 详解
What development models did you know during the interview? Just read this one
Technology sharing | packet capturing analysis TCP protocol
测试优惠券要怎么写测试用例?
MIF file format record
Talk about SOC startup (IX) adding a new board to uboot
Talk about SOC startup (VII) uboot startup process III
Solve the problem that vscode can only open two tabs
Complete collection of common error handling in MySQL installation
Enclosed please find. Net Maui's latest learning resources
Poor math students who once dropped out of school won the fields award this year
【问道】编译原理
The database synchronization tool dbsync adds support for mongodb and es
Automated testing framework
【时间格式工具函数的封装】
Network protocol concept
audit 移植