题目链接

新年好

题目描述

在一个带权无向图中，从1号点出发，需要访问5个指定的亲戚所在的节点。拜访顺序任意，求完成所有拜访所需的最短总时间。

解题思路

这个问题可以看作是一个简化版的旅行商问题 (Traveling Salesman Problem, TSP)。由于需要访问的节点数量非常少（只有5个亲戚），我们可以通过暴力枚举所有可能的拜访顺序来找到最优解。

整个解题过程可以分为两个主要步骤：

1. 预处理：计算关键点之间的最短路径

首先，我们需要知道所有“关键点”之间两两的最短距离。这里的关键点包括家（1号节点）和5个亲戚所在的节点，共6个点。 原图可能包含很多与拜访路线无关的节点和边，直接在原图上搜索所有排列会很复杂。因此，我们先进行预处理：

  • 以每个关键点（家和5个亲戚）为源点，分别运行一次单源最短路径算法。
  • 由于图中所有边的权值（通行时间）都是非负的，我们使用 Dijkstra 算法 是最合适的。
  • 我们需要运行6次 Dijkstra，分别计算出家到所有节点的最短路，以及每个亲戚到所有节点的最短路。
  • 通过这6次计算，我们就可以得到一个 的距离矩阵，其中存储了任意两个关键点之间的最短通行时间。

2. 枚举所有拜访顺序

在获得了关键点之间的最短距离后，问题就变得简单了：

  • 我们需要确定访问5个亲戚的顺序。5个亲戚的全排列共有 种。这是一个很小的数目，完全可以进行暴力枚举。
  • 我们可以使用 next_permutation (C++) 或其他语言的类似工具来生成所有排列。
  • 对于每一种排列（例如，亲戚A -> 亲戚B -> ... -> 亲戚E），我们计算其总路径长度： dist(家, 亲戚A) + dist(亲戚A, 亲戚B) + ... + dist(亲戚D, 亲戚E)
  • 我们遍历所有120种排列，计算出各自的总耗时，并记录下其中的最小值。

最终，这个最小值就是完成所有拜访所需的最短总时间。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;
using ll = long long;
using P = pair<ll, int>;

const ll INF = 1e18;

vector<ll> dijkstra(int start, int n, const vector<vector<P>>& adj) {
    vector<ll> dist(n + 1, INF);
    priority_queue<P, vector<P>, greater<P>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) {
            continue;
        }

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<int> relatives(5);
    vector<int> key_nodes = {1};
    for (int i = 0; i < 5; ++i) {
        cin >> relatives[i];
        key_nodes.push_back(relatives[i]);
    }

    vector<vector<P>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    map<int, vector<ll>> key_node_dists;
    for (int node : key_nodes) {
        key_node_dists[node] = dijkstra(node, n, adj);
    }

    sort(relatives.begin(), relatives.end());
    ll min_total_dist = INF;

    do {
        ll current_dist = 0;
        int last_node = 1;
        for (int relative : relatives) {
            current_dist += key_node_dists[last_node][relative];
            last_node = relative;
        }
        min_total_dist = min(min_total_dist, current_dist);
    } while (next_permutation(relatives.begin(), relatives.end()));

    cout << min_total_dist << endl;

    return 0;
}

import java.util.*;

public class Main {
    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    static class State implements Comparable<State> {
        long dist;
        int u;

        State(long dist, int u) {
            this.dist = dist;
            this.u = u;
        }

        @Override
        public int compareTo(State other) {
            return Long.compare(this.dist, other.dist);
        }
    }

    static long[] dijkstra(int start, int n, List<List<Edge>> adj) {
        long[] dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        PriorityQueue<State> pq = new PriorityQueue<>();

        dist[start] = 0;
        pq.offer(new State(0, start));

        while (!pq.isEmpty()) {
            State current = pq.poll();
            long d = current.dist;
            int u = current.u;

            if (d > dist[u]) {
                continue;
            }

            for (Edge edge : adj.get(u)) {
                int v = edge.to;
                int w = edge.weight;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new State(dist[v], v));
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        List<Integer> relatives = new ArrayList<>();
        List<Integer> keyNodes = new ArrayList<>();
        keyNodes.add(1);
        for (int i = 0; i < 5; i++) {
            int relative = sc.nextInt();
            relatives.add(relative);
            keyNodes.add(relative);
        }

        List<List<Edge>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            adj.get(u).add(new Edge(v, w));
            adj.get(v).add(new Edge(u, w));
        }

        Map<Integer, long[]> keyNodeDists = new HashMap<>();
        for (int node : keyNodes) {
            keyNodeDists.put(node, dijkstra(node, n, adj));
        }

        Collections.sort(relatives);
        long minTotalDist = Long.MAX_VALUE;

        PermutationGenerator permGen = new PermutationGenerator(relatives);
        while (permGen.hasNext()) {
            List<Integer> p = permGen.next();
            long currentDist = 0;
            int lastNode = 1;
            for (int relative : p) {
                currentDist += keyNodeDists.get(lastNode)[relative];
                lastNode = relative;
            }
            minTotalDist = Math.min(minTotalDist, currentDist);
        }
        
        System.out.println(minTotalDist);
    }
}

// Helper class for permutations in Java
class PermutationGenerator {
    private List<Integer> list;
    private int[] p;
    private boolean first = true;

    public PermutationGenerator(List<Integer> list) {
        this.list = new ArrayList<>(list);
        p = new int[list.size()];
        for(int i = 0; i < p.length; i++) p[i] = i;
    }

    public boolean hasNext() {
        if(first) {
            first = false;
            return true;
        }
        return nextPermutation();
    }

    public List<Integer> next() {
        List<Integer> result = new ArrayList<>();
        for (int i : p) {
            result.add(list.get(i));
        }
        return result;
    }

    private boolean nextPermutation() {
        int i = p.length - 2;
        while (i >= 0 && p[i] >= p[i + 1]) {
            i--;
        }
        if (i < 0) return false;

        int j = p.length - 1;
        while (p[j] <= p[i]) {
            j--;
        }
        swap(i, j);
        reverse(i + 1, p.length - 1);
        return true;
    }

    private void swap(int i, int j) {
        int temp = p[i];
        p[i] = p[j];
        p[j] = temp;
    }

    private void reverse(int i, int j) {
        while (i < j) {
            swap(i++, j--);
        }
    }
}

import sys
import heapq
from itertools import permutations

def dijkstra(start, n, adj):
    dist = [float('inf')] * (n + 1)
    pq = [(0, start)]
    dist[start] = 0

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    
    relatives = list(map(int, input().split()))
    key_nodes = [1] + relatives
    
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v, w = map(int, input().split())
        adj[u].append((v, w))
        adj[v].append((u, w))

    key_node_dists = {}
    for node in key_nodes:
        key_node_dists[node] = dijkstra(node, n, adj)

    min_total_dist = float('inf')

    for p in permutations(relatives):
        current_dist = 0
        last_node = 1
        for relative in p:
            current_dist += key_node_dists[last_node][relative]
            last_node = relative
        min_total_dist = min(min_total_dist, current_dist)
        
    print(min_total_dist)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：Dijkstra 算法 + 全排列枚举
  • 时间复杂度：，其中 是关键点数量（）， 是总车站数， 是总公路数。
    • Dijkstra 部分：我们运行 次 Dijkstra，每次复杂度为 ，总计 。
    • 全排列部分：有 种拜访顺序，每种顺序计算耗时需要 次查表。总计 。
    • 由于 是一个很小的常数 (6)，所以总时间复杂度主要由 Dijkstra 部分决定，近似为 。
  • 空间复杂度：，主要用于存储图的邻接表和 Dijkstra 的距离数组。