算法分析

最短路 + dfs

• 通过暴力枚举所有走法共5！,所有每一次走法算一次最短路，得5! * 最短路复杂度

• 因此可以通过空间换时间的方式，先预处理出每个点到其他点的最短路，共求6次最短路，运行复杂度是5! + 最短路复杂度

下面使用的是spfa

时间复杂度 $O(m)$

最坏是$O(nm)$

参考文献

算法提高课

Java 代码

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

public class Main{
    static int N = 50010;
    static int M = 100010 * 2;
    static int m;
    static int n;
    static int INF = 0x3f3f3f3f;
    static boolean[] st = new boolean[N];
    static int[][] dist = new int[6][N];
    static int[] id = new int[N];
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] w = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int ans = INF;
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static void spfa(int start,int[] dist)
    {
        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;
                    }
                }
            }
        }
    }
    //u表示已经走了多少个点，start表示当前点，distance表示已走路程
    static void dfs(int u,int start,int distance)
    {
        //最优性剪枝
        if(distance >= ans) return;
        if(u == 6) 
        {
            ans = distance;
            return;
        }
        for(int i = 1;i < 6;i ++)
        {
            if(st[i]) continue;
            int next = id[i];
            st[i] = true;
            dfs(u + 1,i,distance + dist[start][next]);
            st[i] = false;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        id[0] = 1;
        String[] s2 = br.readLine().split(" ");
        for(int i = 1;i <= 5;i ++) id[i] = Integer.parseInt(s2[i - 1]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            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 ++)   
        {
            spfa(id[i],dist[i]);
        }

        dfs(1,0,0);
        System.out.println(ans);
    }
}