$$\color{Red}{新年好——【提前构图化乘积复杂度为相加】}$$

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

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

解析

一般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

思路

这道题最开始大概看了下y总的思路，觉得难度并不大，于是就自己开始做，大致优化的思路就是，直觉做法，进行dfs枚举组合情况 这道题应该是枚举 五个亲戚站点的全排列，即 5!，然后计算对应情况顺序的最短路之和。那么复杂度相当于，5! * nlog(n)，此时时间复杂度有超时的风险。

那么转化思路，我们只需要开局进行6次堆优化dijkstra，记录这些距离到数组里面，然后我们只需要进行5!的全排列枚举，然后打表求和求最小值即可，相当于优化到5! + 6 * nlog(n)的复杂度。

优化了几十倍左右。

但是做题的时候，我想当然的觉得这个d[][]二维数组，直觉肯定是开d[N][N]这么大，然后后续的枚举过程中，dfs形参我们也是传对应亲戚实际的节点，这么肯定最符合直觉。

但是这么做很坑爹，首先是爆空间了，这个二维数组太大了，这道题不是floyd，不需要每两个点之间的距离，直接只开6个维度，对应存每个节点的dijkstra的距离数组即可。

尤其是想着图省事，把st数组都声明成局部变量在两个方法里面，结果犯了太蠢的错误，dfs里面居然声明局部的st来给全局dfs做递归判断，图省事一时爽，debug火葬场。

我的SPFA全题解

我的Dijkstra全题解

我的Bellman_fold全题解

我的Floyd全题解

java

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


/**
 * @author Fanxy
 */
public class Main {

    private static final int INF = 0x3f3f3f3f;
    static int n, m, idx, N = 50010, M = 100010;
    static int[] h = new int[N];
    static int[] e = new int[2 * M];
    static int[] ne = new int[2 * M];
    static int[] w = new int[2 * M];
    static int[] nodes = new int[6];
    static int[][] d = new int[8][N];
    static boolean [] st = new boolean[6];
    static void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }

    static void dijkstra(int start, int[] d) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        heap.add(new int[]{0, start});
        Arrays.fill(d, INF);
        d[start] = 0;
        boolean[] st = new boolean[N];
        while (!heap.isEmpty()) {
            int node[] = heap.remove();
            int num = node[1];
            int dist = node[0];
            if (st[num]) continue;
            st[num] = true;
            for (int i = h[num]; i != -1; i = ne[i]) {
                int j = e[i];
                if (d[j] > dist + w[i]) {
                    d[j] = dist + w[i];
                    heap.add(new int[]{d[j], j});
                }
            }
        }
    }

    static int dfs(int u, int start, int dist) {
        if (u == 6) return dist;
        int res = INF;
        for (int i = 1; i <= 5; i++) {
            if (!st[i]) {
                st[i] = true;
                int next = nodes[i];
                res = Math.min(res, dfs(u + 1, i, dist + d[start][next]));
                st[i] = false;
            }
        }
        return res;
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        Arrays.fill(h, -1);
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        nodes[0] = 1;
        String[] s2 = br.readLine().split(" ");
        for (int i = 1; i <= 5; i++) nodes[i] = Integer.parseInt(s2[i-1]);
        for (int i = 0; i < m; i++) {
            String[] s3 = br.readLine().split(" ");
            int a = Integer.parseInt(s3[0]);
            int b = Integer.parseInt(s3[1]);
            int c = Integer.parseInt(s3[2]);
            add(a, b, c);
            add(b, a, c);
        }
        for (int i = 0; i < 6; i++) dijkstra(nodes[i], d[i]);
        System.out.println(dfs(1, 0, 0));
    }
}