算法分析

• 枚举所有点作为特定牧场，求特定牧场到所有点的最短距离

点的个数p = 800，边的个数1500

• 朴素版Dijkstra 复杂度是$O(n^3)$ $n^3 = 5.12 * 10^8$

• 堆优化版dijkstra 复杂度是$O(nmlogn)$ $nmlogn = 1.2 * 10^7$

• spfa 复杂度是$O(nm)$ 平均是2到3倍即 $3 * nm = 3.9 * 10^6 $

spfa好强

时间复杂度 $O(nm)$

最坏$O(n^2m)$

参考文献

Java 代码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    static int N = 510;
    static int M = 1460 * 2;
    static int P = 810;
    static int n;
    static int m;
    static int p;
    static int INF = 0x3f3f3f3f;
    static int[] id = new int[N];
    static int[] h = new int[P];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static boolean[] st = new boolean[P];
    static int[] dist = new int[P];
    static int idx = 0;
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static int spfa(int start)
    {
        Queue<Integer> q = new LinkedList<Integer>();
        Arrays.fill(dist, INF);
        dist[start] = 0;
        q.add(start);
        st[start] = true;

        while(!q.isEmpty())
        {
            int t = q.poll();
            st[t] = false;
            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];//获取点编号
                if(dist[j] > dist[t] + w[i])
                {
                    dist[j] = dist[t] + w[i];
                    if(!st[j])
                    {
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }
        int res = 0;
        for(int i = 0;i < n;i ++)
        {
            int j = id[i];
            if(dist[j] == INF) return INF;//可能存在某个点与其他点不连通
            res += dist[j];
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        p = scan.nextInt();
        m = scan.nextInt();
        for(int i = 0;i < n;i ++) id[i] = scan.nextInt();
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            add(a,b,c);
            add(b,a,c);
        }
        int res = INF;
        for(int i = 1;i <= p;i ++) res = Math.min(res, spfa(i));
        System.out.println(res);
    }
}