$$\color{Red}{香甜的黄油——【由复杂度选择合适的图论算法】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

解析

这道题难点不在于选什么算法，其实这道题数据量 n <= 100，选最坏的代码最少的多源最短路 floyd ，也只需要最坏的情况下为 1 * 10 ^ 6，可以在 1秒内ac。

一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，代码中的操作次数控制在 10 ^ 7 ∼ 10 ^ 8 为最佳。

n <= 100 -> O(n ^ 3) -> 状态压缩dp floyd 高斯消元

n <= 1000 -> O(n ^ 2) O(n ^ 2 * log(n)) -> dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford

n ≤ 100000 -> O(nlogn) -> 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa

这道题难点在于能抽象出如何用图论解，第一直觉 -> floyd -> 但复杂度 800 ^ 3 必超时

这种时候就该考虑，用一个复杂度比较合适的单源最短路做 n 次，能否不超时间。

这里使用 spfa 或者 heap dijkstra的情况下，spfa大多数情况下更快，但是有些时候会出现出题人卡数据，故意把一些样例卡到 最坏的 n ^ 2。故求稳可以优先选择 heap dijkstra

我的SPFA全题解

我的Dijkstra全题解

我的Bellman_fold全题解

我的Floyd全题解

SPFA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {

    static int n, p, c, idx, N = 510, M = 810, C = 1460;
    static int[] ids = new int[N];
    static int[] e = new int[2 * C];
    static int[] h = new int[M];
    static boolean[] st = new boolean[M];
    static int[] ne = new int[2 * C];
    static int[] w = new int[2 * C];
    static int[] d = new int[M];
    static final int INF = 0x3f3f3f3f;
    static void add(int a, int b, int c){
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int spfa(int start) {
        Arrays.fill(d, INF);
        d[start] = 0;
        int [] q = new int[N];
        int hh = 0, tt = 1;
        q[hh] = start;

        while (hh != tt){
            int num = q[hh++];
            if (hh == N) hh = 0;
            st[num] = false;
            for (int i = h[num]; i != -1; i=ne[i]) {
                int j = e[i];
                if (d[j] > d[num] + w[i]){
                    d[j] = d[num] + w[i];
                    if (!st[j]){
                        q[tt++] = j;
                        if (tt == N) tt = 0;
                        st[j] = true;
                    }
                }
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (d[ids[i]] != INF) res += d[ids[i]];
            else return INF;
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        String [] s1 = br.readLine().split(" ");
        Arrays.fill(h, -1);

        n = Integer.parseInt(s1[0]);
        p = Integer.parseInt(s1[1]);
        c = Integer.parseInt(s1[2]);
        for (int i = 1; i <= n; i++) ids[i] = Integer.parseInt(br.readLine());

        for (int i = 0; i < c; i++) {
            String [] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            add(a, b, c);
            add(b, a, c);
        }
        int ans = INF;
        for (int i = 1; i <= p; i++) ans = Math.min(ans, spfa(i));
        System.out.println(ans);
    }
}