【最短路】ACwing 1127. 香甜的黄油(堆优化的dijsktra或spfa)

 

  抽象问题：

求所有奶牛到某个点的最短距离和的最小值。

由于是双向的，可以看成从某个点到所有其他点的最短距离的最小值。

所以，可以看成是单源最短路问题，由于是稀疏图且没有负边，所以可以使用堆优化的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);
    }
    
    
}