题解

题面描述

给定一个公园中的 $N$ 个景点（编号从 $0$ 到 $N-1$），以及一个 $N\times N$ 的距离矩阵，矩阵中第 $i$ 行第 $j$ 列的元素表示景点 $i$ 到景点 $j$ 的距离，距离为 $0$ 表示不相邻。还有一行标记哪些景点是公园的出入口（用 $1$ 表示是，$0$ 表示否）。最后给定一个入口景点编号 $S$ 和一个出口景点编号 $T$。要求在允许经过任意其他景点但不需要访问所有景点的前提下，找到从 $S$ 到 $T$ 的最短游园线路，并输出具体经过的景点序列。如果存在多条等长最短路径，则输出按景点序号从小到大最小的那条路径。

思路

1. 将景点和距离看作一个无向带权图，节点数为 $N$，边权由距离矩阵给出。
2. 使用 Dijkstra 算法 从起点 $S$ 计算到每个节点的最短距离 $dist[i]$。
3. 为了在距离相同的情况下选择 字典序最小 的路径，我们在松弛操作中不仅维护距离，还需要维护到达该节点的路径序列 $path[i]$。
4. 松弛时若新的距离更小，直接更新；若新的距离等于当前最优距离，则比较两个路径序列的字典序，选择更小者。
5. 最终输出 $path[T]$ 即为所求路径。

算法步骤

• 初始化：对所有 $i$，$dist[i]=\infty$, $path[i]=\{\}$；令 $dist[S]=0$, $path[S]=\{S\}$。
• 使用优先队列（最小堆）存储 $(dist,\,node)$，初始压入 $(0,\,S)$。
• 当队列非空时，取出距离最小的 $(d,u)$，若 $d>dist[u]$ 则跳过；否则对所有 $v$（满足 $g[u][v]>0$）尝试松弛：
  • 若 $dist[u] + g[u][v] < dist[v]$，则$$dist[v] \leftarrow dist[u] + g[u][v]$$ $$path[v] \leftarrow path[u]\ \text{加上}\ v$$
  • 否则若$$dist[u] + g[u][v] = dist[v]$$ 则比较新路径 $path[u] + \{v\}$ 与旧路径 $path[v]$ 的字典序，若前者更小，则用前者更新 $path[v]$。
  • 若发生更新，则将 $(dist[v],\,v)$ 压入队列。
• 结束后，输出 $path[T]$。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> g(N, vector<int>(N));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> g[i][j];

    vector<int> isEntrance(N);
    for (int i = 0; i < N; i++)
        cin >> isEntrance[i];

    int S, T;
    cin >> S >> T;

    const int INF = INT_MAX / 2;
    vector<int> dist(N, INF);
    vector<vector<int>> path(N);

    // 最小堆，存 (距离, 节点)
    using pii = pair<int,int>;
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[S] = 0;
    path[S] = {S};
    pq.emplace(0, S);

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (int v = 0; v < N; v++) {
            if (g[u][v] == 0) continue; // 不相邻
            int nd = d + g[u][v];
            vector<int> newPath = path[u];
            newPath.push_back(v);

            if (nd < dist[v] ||
               (nd == dist[v] && newPath < path[v])) {
                dist[v] = nd;
                path[v] = newPath;
                pq.emplace(nd, v);
            }
        }
    }

    // 输出路径
    for (int i = 0; i < (int)path[T].size(); i++) {
        if (i) cout << ' ';
        cout << path[T][i];
    }
    return 0;
}

Python

import heapq

def shortest_path(N, g, is_entrance, S, T):
    INF = float('inf')
    dist = [INF] * N
    paths = [[] for _ in range(N)]

    dist[S] = 0
    paths[S] = [S]
    pq = [(0, S)]  # (距离, 节点)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v in range(N):
            if g[u][v] == 0:
                continue  # 不相邻
            nd = d + g[u][v]
            new_path = paths[u] + [v]
            # 如果新的距离更短，或距离相同但字典序更小，则更新
            if nd < dist[v] or (nd == dist[v] and new_path < paths[v]):
                dist[v] = nd
                paths[v] = new_path
                heapq.heappush(pq, (nd, v))
    return paths[T]

# 读入
N = int(input())
g = [list(map(int, input().split())) for _ in range(N)]
is_entrance = list(map(int, input().split()))
S, T = map(int, input().split())

# 计算并输出
res = shortest_path(N, g, is_entrance, S, T)
print(' '.join(map(str, res)))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] g = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                g[i][j] = sc.nextInt();

        int[] isEntrance = new int[N];
        for (int i = 0; i < N; i++)
            isEntrance[i] = sc.nextInt();

        int S = sc.nextInt(), T = sc.nextInt();
        final int INF = Integer.MAX_VALUE / 2;
        int[] dist = new int[N];
        List<List<Integer>> paths = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            dist[i] = INF;
            paths.add(new ArrayList<>());
        }

        dist[S] = 0;
        paths.get(S).add(S);
        // 优先队列，按 (距离, 节点) 升序排列
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            Comparator.<int[]>comparingInt(a -> a[0])
                      .thenComparingInt(a -> a[1])
        );
        pq.offer(new int[]{0, S});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], u = cur[1];
            if (d > dist[u]) continue;
            for (int v = 0; v < N; v++) {
                if (g[u][v] == 0) continue; // 不相邻
                int nd = d + g[u][v];
                List<Integer> newPath = new ArrayList<>(paths.get(u));
                newPath.add(v);
                if (nd < dist[v] || (nd == dist[v] && lexLess(newPath, paths.get(v)))) {
                    dist[v] = nd;
                    paths.set(v, newPath);
                    pq.offer(new int[]{nd, v});
                }
            }
        }

        // 输出结果
        List<Integer> ans = paths.get(T);
        for (int i = 0; i < ans.size(); i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(ans.get(i));
        }
    }

    // 比较两条路径的字典序
    private static boolean lexLess(List<Integer> a, List<Integer> b) {
        int n = Math.min(a.size(), b.size());
        for (int i = 0; i < n; i++) {
            if (!a.get(i).equals(b.get(i))) {
                return a.get(i) < b.get(i);
            }
        }
        return a.size() < b.size();
    }
}

题目内容

某公园每年都会在新年时举办灯会，由于公园面积很大目各景点分散，希望你设计一条游园线路,从某个指定入口景点开始，到某个指定出口景点结束，使得游园总路程最短。最短路线不需要走完所有的景点，目中间允许经过其他出入口景点而不离开公园。

输入描述

第一行:N，景点个数，景点序号从$0$开始，$N-1$结束。$2<=N<=15$

第二行至第$N+1$行:是一个$N*N$的矩阵，表示各相邻景点之间的距离，距离为$0$表示不相邻。

第$N+2$行:该景点是否是公园出入口($1$-是，$0$-否)。

第$N+3$行:要计算最短线路的入口景点序号和出口景点序号

所有用例的输入确保一定存在符合条件的线路，你无需考虑无解的情况。

输出描述

具体游园线路，如果有多条符合条件的线路，按景点序号从小到大进行排序。

样例1

输入

3
0 2 4
2 0 3
4 3 0
1 0 1
0 2

输出

0 2

说明

不难看出线路$0->2$是最短的

样例2

输入

4
0 2 0 3
2 0 3 1
0 3 0 4
3 1 4 0
1 0 1 0
0 2

输出

0 1 2

说明

不难看出符合要求的线路:

$0->1->2$,长度为$5$