题解

题面描述

给定一个地铁线路网络，其中有$N$个站点（$3 \le N \le 20$）以及各个相邻站点之间的乘坐时间。输入中：

• 第一行为站点总数$N$；
• 第二行为乘客的出发站$s$和到达站$t$；
• 接下来的若干行每行给出两个站点和它们之间的乘坐时间，输入持续到出现结束符$"0000"$为止。

本题中地铁网络被视为无向图，即每条输入的边可以双向使用。保证输入中起点与终点之间存在唯一一条耗时最短的路径。要求程序输出由各站点名称组成、以空格分隔的完整最短路径线路。

解题思路

• 构图：
  将输入数据构造为一个无向图。每个站点作为图中的节点，每条输入边对应两个方向的边（即$u \to v$和$v \to u$），边的权值均为乘坐时间$w$。

• 算法选择：
  使用$Dijkstra$算法求解从出发站$s$到终点$t$的最短时间路径。由于各边权均为正值，$Dijkstra$能够高效地给出正确解。

• 路径还原：
  在执行$Dijkstra$过程中记录每个节点的前驱节点，最终利用该前驱记录由终点回溯到起点，再反转得到完整的最短路径。

代码分析

1. 变量定义：

   • 站点总数用变量$N$表示；
   • 出发站和到达站分别用$s$和$t$表示；
   • 图采用邻接表形式存储（例如$unordered\_map$、$dict$或$HashMap$），存储每个节点的邻边及对应乘坐时间。

2. 无向边构造：
   读入每条边数据时，分别添加$u \to v$和$v \to u$两个方向的边。

3. $Dijkstra$算法实现：

   • 初始化距离映射$dist$（所有站点距离设为无穷大$\infty$，起点$s$距离置为$0$），并构造前驱记录映射$prev$；
   • 利用优先队列维护当前最短路径候选，更新相邻边时检查是否可以用更小的距离更新终点的距离，并记录前驱节点。

4. 问题本质：
   本题归结为图论中的单源最短路径问题，核心在于如何正确构造无向图以及利用$$Dijkstra$$算法计算最短距离并恢复最短路径。

$C++$ 参考代码

#include <iostream>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <limits>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

// 定义边结构体，表示两个节点之间的乘坐时间
struct Edge {
    char to;      // 目的节点
    int time;     // 乘坐时间
};

int main(){
    int N;
    cin >> N; // 输入站点总数N
    
    char start, end;
    cin >> start >> end; // 输入出发站s和到达站t
    
    // 构造无向图，使用邻接表存储，每个输入边添加两个方向的边
    unordered_map<char, vector<Edge>> graph;
    while(true){
        string u_str;
        cin >> u_str;  // 如果遇到结束符"0000"则退出
        if(u_str == "0000") break;
        char u = u_str[0];
        char v;
        int t;
        cin >> v >> t; // 读取两个站点和乘坐时间w
        graph[u].push_back({v, t});
        graph[v].push_back({u, t}); // 添加反向边
    }
    
    // 初始化距离映射和前驱映射
    unordered_map<char, int> dist;
    unordered_map<char, char> prev;
    const int INF = numeric_limits<int>::max(); // 设定无穷大INF
    // 确保图中每个涉及的节点都在距离映射中
    for(auto &entry : graph){
        dist[entry.first] = INF;
        for(auto edge : entry.second){
            if(dist.find(edge.to) == dist.end()){
                dist[edge.to] = INF;
            }
        }
    }
    dist[start] = 0; // 起点距离置为0
    
    // 定义优先队列，按照距离从小到大排序
    using pii = pair<int, char>; // 表示(距离, 节点)
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    
    // Dijkstra 算法核心循环
    while(!pq.empty()){
        auto [current_time, cur] = pq.top();
        pq.pop();
        if(current_time > dist[cur]) continue;
        // 遍历当前节点的所有出边
        for(auto edge : graph[cur]){
            char next = edge.to;
            int new_time = current_time + edge.time;
            if(new_time < dist[next]){
                dist[next] = new_time;
                prev[next] = cur; // 记录前驱节点
                pq.push({new_time, next});
            }
        }
    }
    
    // 使用前驱映射还原完整最短路径
    vector<char> path;
    for(char cur = end; cur != start; cur = prev[cur])
        path.push_back(cur);
    path.push_back(start);
    reverse(path.begin(), path.end());
    
    // 输出站点路径，站点之间用空格分隔
    for(size_t i = 0; i < path.size(); i++){
        cout << path[i];
        if(i != path.size() - 1)
            cout << " ";
    }
    cout << endl;
    
    return 0;
}

$Python$ 参考代码

import sys
import heapq

# 读取所有输入数据
lines = sys.stdin.read().strip().splitlines()
# 第一行：站点总数N
N = int(lines[0])
# 第二行：出发站s和到达站t
start, end = lines[1].split()
start = start.strip()
end = end.strip()

# 构造无向图，使用字典存储邻接边 (目的站, 乘坐时间)
graph = {}
i = 2
while i < len(lines):
    if lines[i].strip() == "0000":
        break
    parts = lines[i].split()
    u = parts[0].strip()
    v = parts[1].strip()
    t = int(parts[2])
    # 添加 u -> v 的边
    if u not in graph:
        graph[u] = []
    graph[u].append((v, t))
    # 添加 v -> u 的边（无向图）
    if v not in graph:
        graph[v] = []
    graph[v].append((u, t))
    i += 1

# 初始化距离字典和前驱字典
INF = float('inf')
dist = {}
prev = {}
# 确保图中所有涉及的节点都在距离字典中
for u in graph:
    if u not in dist:
        dist[u] = INF
    for (v, time) in graph[u]:
        if v not in dist:
            dist[v] = INF

dist[start] = 0

# 使用 heapq 实现优先队列，存储格式为 (距离, 节点)
pq = [(0, start)]
while pq:
    current_time, cur = heapq.heappop(pq)
    if current_time > dist[cur]:
        continue
    # 遍历当前节点的所有出边
    for (next_node, w) in graph[cur]:
        new_time = current_time + w
        if new_time < dist[next_node]:
            dist[next_node] = new_time
            prev[next_node] = cur
            heapq.heappush(pq, (new_time, next_node))

# 利用前驱字典回溯恢复完整最短路径
path = []
cur = end
while cur != start:
    path.append(cur)
    cur = prev[cur]
path.append(start)
path.reverse()

# 输出最短路径，站点之间空格分隔
print(" ".join(path))

$Java$ 参考代码

import java.util.*;
import java.io.*;

public class MetroShortestPath {
    // 定义边的类，包含目的站点和乘坐时间
    static class Edge {
        char to;     // 目的站点
        int time;    // 乘坐时间

        public Edge(char to, int time) {
            this.to = to;
            this.time = time;
        }
    }
    
    // 用于优先队列中，存储(距离, 节点)对
    static class Node implements Comparable<Node> {
        char station;
        int distance;
        
        Node(char station, int distance) {
            this.station = station;
            this.distance = distance;
        }
        
        public int compareTo(Node other) {
            return this.distance - other.distance;
        }
    }
    
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        // 读取站点总数N
        int N = sc.nextInt();
        // 读取出发站s和到达站t
        char start = sc.next().charAt(0);
        char end = sc.next().charAt(0);
        
        // 构造无向图，使用 HashMap 存储每个节点的邻接边，两条边表示无向边
        Map<Character, List<Edge>> graph = new HashMap<>();
        while (sc.hasNext()) {
            String token = sc.next();
            if (token.equals("0000"))
                break;
            char u = token.charAt(0);
            char v = sc.next().charAt(0);
            int t = sc.nextInt();
            // 添加 u -> v 的边
            if (!graph.containsKey(u)) {
                graph.put(u, new ArrayList<>());
            }
            graph.get(u).add(new Edge(v, t));
            // 添加 v -> u 的边（无向图）
            if (!graph.containsKey(v)) {
                graph.put(v, new ArrayList<>());
            }
            graph.get(v).add(new Edge(u, t));
        }
        
        // 初始化距离映射和前驱映射
        Map<Character, Integer> dist = new HashMap<>();
        Map<Character, Character> prev = new HashMap<>();
        final int INF = Integer.MAX_VALUE;
        
        // 确保所有涉及的节点均被初始化
        for (Character u : graph.keySet()) {
            dist.put(u, INF);
            for (Edge edge : graph.get(u)) {
                if (!dist.containsKey(edge.to)) {
                    dist.put(edge.to, INF);
                }
            }
        }
        dist.put(start, 0); // 出发站距离设为0
        
        // 使用优先队列实现 Dijkstra 算法
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        
        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            char cur = curNode.station;
            int current_time = curNode.distance;
            if (current_time > dist.get(cur))
                continue;
            if (graph.containsKey(cur)) {
                for (Edge edge : graph.get(cur)) {
                    char next = edge.to;
                    int new_time = current_time + edge.time;
                    if (new_time < dist.get(next)) {
                        dist.put(next, new_time);
                        prev.put(next, cur);
                        pq.add(new Node(next, new_time));
                    }
                }
            }
        }
        
        // 利用前驱映射恢复完整最短路径
        List<Character> path = new ArrayList<>();
        for (char cur = end; cur != start; cur = prev.get(cur)) {
            path.add(cur);
        }
        path.add(start);
        Collections.reverse(path);
        
        // 输出最短路径，各站点之间以空格分隔
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < path.size(); i++) {
            sb.append(path.get(i));
            if(i != path.size() - 1)
                sb.append(" ");
        }
        System.out.println(sb.toString());
        
        sc.close();
    }
}

题目内容

大湾区某城市地铁线路非常密集，乘客很难一眼看出选择哪条线路乘型比较合适，为了解决这个问题，地铁公司希望你开发一个程序帮助乘客挑选合适的乘坐线路，使得乘坐时间最短，地铁公司可以提供的数据是各相邻站点之间的乘坐时间。

输入描述

第一行:$N$，站点总数,$3<=N<=20$.

第二行:乘客的出发和到达站点。

第三行起:相邻站点之间的乘坐时间，每对站点一行，站点名称是单个小写字母，站点名一定包括出发和到达站点，输入保证只有一个唯一解;

结束行:$0000$

输出描述

耗时最短的线路

样例1

输入

12
a e
a b 2
b c 2
c d 2
d e 2
f b 3
b g 3
g h 2
h i 3
j h 2 
h e 3
e k 2
k l 4
0000

输出

a b c d e

说明

输入对应的地铁图如下:

线路а->b->c->d->e耗时最短

样例2

输入

12
f k
a b 2
b c 2
c d 2
d e 2
f b 3
b g 3
g h 2
h i 3
j h 2
h e 3
e k 2
k l 4
0000

输出

f b c d e k

说明

输入对应的地铁图如下:

f->b->c->d->e->K是耗时最短的线路