题解

题目描述

已知 A 市运营了 $N$ 条地铁线路，市民在乘坐地铁时单条线路通票 2 元，换乘一次加 1 元。给出 $N$ 条线路的所有站名列表，请帮乘客寻找从出发站到目的站最便宜的地铁换乘方案，并输出票价。每条地铁线路不包含环路（即没有相同站名）。不同线路中相同的站点名表示可以在该站点换乘。输入保证若可达则唯一解。

• 输入

  • 第一行：地铁线路个数 $N$，范围 $[1,1000]$
  • 接下来的 $N$ 行：第 $i$ 条线路依次包含的站名（站名间用空格分隔，每个站名长度 $\le100$，每条线路站点数 $\le100$）
  • 第 $N+2$ 行：出发站和目的站，用空格分隔

• 输出

  • 若存在方案，第一行按“出发站-换乘站(可多)-目的站”格式输出换乘方案，第二行输出总票价。
  • 若不可达，只输出一行 NA。

思路

1. 建图模型

   • 将每个线路上的每个站点视为一个状态，状态用 $(\text{line},\text{pos})$ 表示；
   • 同一线路上相邻站点间的移动视为“权重 0”边；
   • 同一站点在不同线路间的换乘视为“权重 1”边。

2. 最少换乘次数

   • 初始从所有包含出发站的状态出发，使用 0-1 BFS（双端队列）在上述图中搜索，计算到达每个状态的最少换乘次数 $d[\text{line}][\text{pos}]$；
   • 当到达目的站对应的任一状态时即可停止，题目保证唯一最优解。

3. 路径回溯

   • 搜索过程中记录每个状态的前驱状态 $\mathrm{pre}[\text{line}][\text{pos}]$；
   • 从终点状态反向回溯到起点，得到完整的状态路径；
   • 按路径中线路编号变化提取出所有换乘站。

4. 票价计算

   • 票价 $=\;2\;+\;\bigl(\text{换乘次数}\bigr)$，其中换乘次数即最少换乘次数。

cpp

#include <bits/stdc++.h>
using namespace std;
struct S{ int l,p,t; }; // l: 线号, p: 位置, t: 换乘数
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin>>N; cin.ignore();
    vector<vector<string>> L(N);
    for(int i=0;i<N;i++){
        string ln; getline(cin,ln);
        istringstream ss(ln);
        string st;
        while(ss>>st) L[i].push_back(st);
    }
    string A,B; cin>>A>>B;
    unordered_map<string,vector<pair<int,int>>> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<(int)L[i].size();j++)
            M[L[i][j]].push_back({i,j});
    if(!M.count(A)||!M.count(B)){
        cout<<"NA"; return 0;
    }
    const int INF = 1e9;
    vector<vector<int>> D(N);
    vector<vector<pair<int,int>>> P(N);
    for(int i=0;i<N;i++){
        D[i].assign(L[i].size(),INF);
        P[i].assign(L[i].size(),{-1,-1});
    }
    deque<S> dq;
    for(auto &pr:M[A]){
        int l=pr.first, p=pr.second;
        D[l][p]=0;
        dq.push_back({l,p,0});
    }
    bool ok=false; int el,ep;
    while(!dq.empty()){
        auto c=dq.front(); dq.pop_front();
        if(L[c.l][c.p]==B){
            ok=true; el=c.l; ep=c.p; break;
        }
        if(c.t> D[c.l][c.p]) continue;
        // 同线移动
        if(c.p>0 && c.t< D[c.l][c.p-1]){
            D[c.l][c.p-1]=c.t;
            P[c.l][c.p-1]={c.l,c.p};
            dq.push_front({c.l,c.p-1,c.t});
        }
        if(c.p+1<(int)L[c.l].size() && c.t< D[c.l][c.p+1]){
            D[c.l][c.p+1]=c.t;
            P[c.l][c.p+1]={c.l,c.p};
            dq.push_front({c.l,c.p+1,c.t});
        }
        // 换乘
        string cur=L[c.l][c.p];
        for(auto &pr:M[cur]){
            int nl=pr.first, np=pr.second;
            if(nl==c.l) continue;
            if(c.t+1< D[nl][np]){
                D[nl][np]=c.t+1;
                P[nl][np]={c.l,c.p};
                dq.push_back({nl,np,c.t+1});
            }
        }
    }
    if(!ok){
        cout<<"NA"; return 0;
    }
    // 回溯
    vector<pair<int,int>> path;
    for(int l=el,p=ep; l!=-1; ){
        path.push_back({l,p});
        auto pr=P[l][p];
        l=pr.first; p=pr.second;
    }
    reverse(path.begin(),path.end());
    // 提取站点：出发-换乘-目的
    vector<string> R;
    int pl=path[0].first, pp=path[0].second;
    R.push_back(L[pl][pp]);
    for(int i=1;i<(int)path.size();i++){
        int cl=path[i].first, cp=path[i].second;
        if(cl!=pl) R.push_back(L[cl][cp]);
        pl=cl; pp=cp;
    }
    if(R.back()!=B) R.push_back(B);
    int tr=(int)R.size()-2;
    int fare=2+tr;
    for(int i=0;i<(int)R.size();i++){
        cout<<R[i]<<(i+1==(int)R.size()?"":"-");
    }
    cout<<"\n"<<fare;
    return 0;
}

python

# Python 3 实现
import sys
from collections import deque, defaultdict
def main():
    input = sys.stdin.readline
    N = int(input().strip())
    lines = []
    for _ in range(N):
        lines.append(input().strip().split())
    A, B = input().split()
    # 站名 -> [(线号, 位置), ...]
    M = defaultdict(list)
    for i, ln in enumerate(lines):
        for j, st in enumerate(ln):
            M[st].append((i, j))
    if A not in M or B not in M:
        print("NA")
        return
    INF = 10**9
    # D[i][j]: 到达线 i、位置 j 的最小换乘数
    D = [ [INF]*len(lines[i]) for i in range(N) ]
    # P 用于回溯前驱 (prev_line, prev_pos)
    P = [ [(-1, -1)]*len(lines[i]) for i in range(N) ]
    dq = deque()
    # 多源起点
    for l, p in M[A]:
        D[l][p] = 0
        dq.append((l, p, 0))
    found = False
    end = (-1, -1)
    while dq:
        l, p, t = dq.popleft()
        # 找到终点
        if lines[l][p] == B:
            found = True
            end = (l, p)
            break
        if t > D[l][p]:
            continue
        # 同线前后移动（权重0）
        for np in (p-1, p+1):
            if 0 <= np < len(lines[l]) and t < D[l][np]:
                D[l][np] = t
                P[l][np] = (l, p)
                dq.appendleft((l, np, t))
        # 换乘（权重1）
        for nl, np in M[lines[l][p]]:
            if nl == l: continue
            if t+1 < D[nl][np]:
                D[nl][np] = t+1
                P[nl][np] = (l, p)
                dq.append((nl, np, t+1))
    if not found:
        print("NA")
        return
    # 回溯路径
    path = []
    l, p = end
    while l != -1:
        path.append((l, p))
        l, p = P[l][p]
    path.reverse()
    # 提取换乘站序列
    route = [ lines[path[0][0]][path[0][1]] ]
    prev_l = path[0][0]
    for l, p in path[1:]:
        if l != prev_l:
            route.append(lines[l][p])
        prev_l = l
    if route[-1] != B:
        route.append(B)
    # 计算票价
    transfers = len(route) - 2
    fare = 2 + transfers
    print("-".join(route))
    print(fare)
if __name__ == "__main__":
    main()

java

// Java 实现
import java.io.*;
import java.util.*;
public class Main {
    static class State {
        int l, p, t;
        State(int l, int p, int t) { this.l = l; this.p = p; this.t = t; }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        List<List<String>> lines = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            lines.add(Arrays.asList(br.readLine().trim().split("\\s+")));
        }
        String[] ab = br.readLine().split("\\s+");
        String A = ab[0], B = ab[1];
        // 站名 -> List of (线号, 位置)
        Map<String, List<int[]>> M = new HashMap<>();
        for (int i = 0; i < N; i++) {
            List<String> ln = lines.get(i);
            for (int j = 0; j < ln.size(); j++) {
                M.computeIfAbsent(ln.get(j), k -> new ArrayList<>()).add(new int[]{i, j});
            }
        }
        if (!M.containsKey(A) || !M.containsKey(B)) {
            System.out.println("NA");
            return;
        }
        final int INF = 1_000_000_000;
        int[][] D = new int[N][];
        int[][][] P = new int[N][][];
        for (int i = 0; i < N; i++) {
            int sz = lines.get(i).size();
            D[i] = new int[sz];
            P[i] = new int[sz][2];
            Arrays.fill(D[i], INF);
            for (int j = 0; j < sz; j++) {
                P[i][j][0] = P[i][j][1] = -1;
            }
        }
        Deque<State> dq = new ArrayDeque<>();
        for (int[] pr : M.get(A)) {
            int l = pr[0], p = pr[1];
            D[l][p] = 0;
            dq.addLast(new State(l, p, 0));
        }
        boolean found = false;
        int el = -1, ep = -1;
        while (!dq.isEmpty()) {
            State cur = dq.pollFirst();
            int l = cur.l, p = cur.p, t = cur.t;
            if (lines.get(l).get(p).equals(B)) {
                found = true; el = l; ep = p; break;
            }
            if (t > D[l][p]) continue;
            // 同线移动（权重0）
            for (int np : new int[]{p-1, p+1}) {
                if (np >= 0 && np < lines.get(l).size() && t < D[l][np]) {
                    D[l][np] = t;
                    P[l][np] = new int[]{l, p};
                    dq.addFirst(new State(l, np, t));
                }
            }
            // 换乘（权重1）
            String curSt = lines.get(l).get(p);
            for (int[] pr : M.get(curSt)) {
                int nl = pr[0], np = pr[1];
                if (nl == l) continue;
                if (t + 1 < D[nl][np]) {
                    D[nl][np] = t + 1;
                    P[nl][np] = new int[]{l, p};
                    dq.addLast(new State(nl, np, t + 1));
                }
            }
        }
        if (!found) {
            System.out.println("NA");
            return;
        }
        // 回溯
        List<int[]> path = new ArrayList<>();
        int l = el, p = ep;
        while (l != -1) {
            path.add(new int[]{l, p});
            int nl = P[l][p][0], np = P[l][p][1];
            l = nl; p = np;
        }
        Collections.reverse(path);
        // 提取路线
        List<String> route = new ArrayList<>();
        int prevL = path.get(0)[0], prevP = path.get(0)[1];
        route.add(lines.get(prevL).get(prevP));
        for (int i = 1; i < path.size(); i++) {
            int cl = path.get(i)[0], cp = path.get(i)[1];
            if (cl != prevL) {
                route.add(lines.get(cl).get(cp));
            }
            prevL = cl; prevP = cp;
        }
        if (!route.get(route.size()-1).equals(B)) {
            route.add(B);
        }
        int transfers = route.size() - 2;
        int fare = 2 + transfers;
        System.out.println(String.join("-", route));
        System.out.println(fare);
    }
}

题目内容

已知 $A$ 市运营了 $N$ 条地铁线路，市民在乘坐地铁时单条线路通票 $2$ 元，换乘一次加 $1$ 元。给出 $N$ 条线路的所有站名列表，请帮乘客寻找从出发站到目的站最便官的地铁换乘方案，并输出票价。每条地铁线路不包含环路，即没有相同站名。

输入描述

第一行为地铁线路个数 $N$ ，范围是 $[1,1000]$；

第二行 到 $N+1$ 行：每条线路依次包含的站名，每个站名包含的字符个数不超过 $100$ ，站点个数也不超过 $100$ ，依次用空格隔开，不同线路中相同的站点名表示是一个换乘站；

第 $N+2$ 行，出发站和目的站，用空格隔开。

输入保证：若可达则为唯一解。

输出描述

第一行按照出发站-换乘站(可以是多个)-目的站的格式输出换乘方案的字符串;

第二行输出换乘方案的总票价。

如果没有任何方案可实现出发站到目的站，只输出一行： $NA$ 。

样例1

输入

3
A B C D F
C E G H
B G I J
A J

输出

A-B-J
3

说明

从出发站 $A$ 到目的站 $J$ 有两个方案：一号线到 $C$ 站后换乘二号线，到 $G$ 站后换乘三号线到 $J$ 站，换乘两次，总票价 $4$ 元；一号线到 $B$ 站后换乘三号线到 $J$ 站，换乘一次，总票价 $3$ 元。因此按照第二个方案愉出。

样例2

输入

3
A B C D F
E G H
G I J
A J

输出

NA

说明

从出发站 $A$ 所在的一号线没有任何一个换乘站可以到二号线和三号线，因此没有方案抵达目的站 $J$ ，输出 $NA$ 。