解题思路

给定若干条电车线路，每条线路有固定票价 price，并给出它依次经过的一组站点。上车一次只收该线路的固定票价，在线路内任意移动不再收费；在换乘点（出现在多条线路中的同一站点）换乘到另一条线路时，需要再付那条线路的票价。求从起点站 X 到终点站 Y 的最小总票价；若不可达或最小票价大于身上钱数 Z，输出 -1。

建模与算法

• 将“站点内免费移动、换乘才付费”转化为线路图： 把每一条电车线路看作图中的一个节点；若两条线路有共同站点，则在它们之间连一条无权边。
• 费用在“进入一条线路时支付”。因此可在节点带权图上跑最短路： 初始把所有包含起点 X 的线路加入优先队列，起始代价为该线路的 price；从一条线路 u 走到相邻线路 v 的代价增量是 price[v]。当弹出队首线路已包含终点 Y 时，其代价就是最小总票价。
• 算法可用 Dijkstra（对非负权）实现；由于 M ≤ 50，构图也可用“站点 → 所属线路列表”的映射快速建立相邻关系。

复杂度分析

• 设线路数为 M (≤50)，每条线路经过站点数不超过 10。
• 建图：把每个站点出现的所有线路两两相连，总体 O(总站点出现次数 + M²)，数据范围下极小。
• Dijkstra：O(M log M)。
• 额外空间：存图与队列，O(M)。

代码实现

Python

# 题面功能：给出线路与价格，求从X到Y的最小总票价；若不可达或超过Z则输出-1
import sys
import heapq

def min_cost(M, X, Y, Z, lines):
    # lines: List[(price, [stations...])]
    # 1) 站点 -> 线路索引列表
    station_to_lines = {}
    for i, (price, stations) in enumerate(lines):
        for s in stations:
            station_to_lines.setdefault(s, []).append(i)

    # 2) 建立“线路图”邻接表（两条线路若有公共站点则相连）
    adj = [set() for _ in range(M)]
    for _, idxs in station_to_lines.items():
        for i in idxs:
            for j in idxs:
                if i != j:
                    adj[i].add(j)

    # 3) Dijkstra：进入一条线路需要支付它的price
    INF = 10**18
    dist = [INF] * M
    start_lines = station_to_lines.get(X, [])
    target_lines = set(station_to_lines.get(Y, []))
    if not start_lines or not target_lines:
        return -1

    pq = []
    for i in start_lines:
        dist[i] = lines[i][0]  # 上第一条包含X的线路需付它的票价
        heapq.heappush(pq, (dist[i], i))

    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue
        if u in target_lines:          # 该线路包含Y，当前代价即最小票价
            return d if d <= Z else -1
        for v in adj[u]:
            nd = d + lines[v][0]       # 换乘到v，需要支付v的票价
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return -1

def main():
    data = list(map(int, sys.stdin.read().split()))
    it = iter(data)
    M = next(it); X = next(it); Y = next(it); Z = next(it)
    lines = []
    for _ in range(M):
        price = next(it)
        n = next(it)
        stations = [next(it) for _ in range(n)]
        lines.append((price, stations))
    ans = min_cost(M, X, Y, Z, lines)
    print(ans)

if __name__ == "__main__":
    main()

Java

// ACM风格：输入输出在main里，核心逻辑在外部函数；类名固定为Main
import java.util.*;

public class Main {
    // 求最小总票价；不可达或超过Z则返回-1
    static int minCost(int M, int X, int Y, int Z, int[] price, List<List<Integer>> lineStations) {
        // 1) 站点 -> 线路索引列表
        Map<Integer, List<Integer>> stationToLines = new HashMap<>();
        for (int i = 0; i < M; i++) {
            for (int s : lineStations.get(i)) {
                stationToLines.computeIfAbsent(s, k -> new ArrayList<>()).add(i);
            }
        }
        // 2) 邻接关系：两条线路有共同站点则相邻
        List<Set<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < M; i++) adj.add(new HashSet<>());
        for (List<Integer> idxs : stationToLines.values()) {
            int sz = idxs.size();
            for (int i = 0; i < sz; i++) {
                for (int j = 0; j < sz; j++) {
                    if (i != j) adj.get(idxs.get(i)).add(idxs.get(j));
                }
            }
        }

        List<Integer> start = stationToLines.get(X);
        List<Integer> target = stationToLines.get(Y);
        if (start == null || target == null) return -1;
        boolean[] isTarget = new boolean[M];
        for (int t : target) isTarget[t] = true;

        // 3) Dijkstra：进入一条线路即付该线路票价
        long INF = (long)1e18;
        long[] dist = new long[M];
        Arrays.fill(dist, INF);
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));

        for (int s : start) {
            dist[s] = price[s];
            pq.offer(new long[]{dist[s], s});
        }

        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long d = cur[0];
            int u = (int)cur[1];
            if (d != dist[u]) continue;
            if (isTarget[u]) return d <= Z ? (int)d : -1;
            for (int v : adj.get(u)) {
                long nd = d + price[v]; // 换乘到v要支付v的票价
                if (nd < dist[v]) {
                    dist[v] = nd;
                    pq.offer(new long[]{nd, v});
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt(), X = sc.nextInt(), Y = sc.nextInt(), Z = sc.nextInt();
        int[] price = new int[M];
        List<List<Integer>> lineStations = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            int p = sc.nextInt(), n = sc.nextInt();
            price[i] = p;
            List<Integer> st = new ArrayList<>();
            for (int k = 0; k < n; k++) st.add(sc.nextInt());
            lineStations.add(st);
        }
        int ans = minCost(M, X, Y, Z, price, lineStations);
        System.out.println(ans);
        sc.close();
    }
}

C++

// ACM风格：读入->主函数，核心逻辑放外部函数；注释中文说明思路
#include <bits/stdc++.h>
using namespace std;

// 求最小总票价；不可达或超过Z则返回-1
int min_cost(int M, int X, int Y, int Z,
             const vector<int>& price,
             const vector<vector<int>>& lineStations) {
    // 1) 站点 -> 线路索引列表
    unordered_map<int, vector<int>> stationToLines;
    for (int i = 0; i < M; ++i) {
        for (int s : lineStations[i]) stationToLines[s].push_back(i);
    }

    // 2) 建邻接：两条线路若有公共站点则相连
    vector<vector<int>> adj(M);
    for (auto &kv : stationToLines) {
        const vector<int>& idxs = kv.second;
        for (int i = 0; i < (int)idxs.size(); ++i) {
            for (int j = 0; j < (int)idxs.size(); ++j) {
                if (i != j) adj[idxs[i]].push_back(idxs[j]);
            }
        }
    }

    if (!stationToLines.count(X) || !stationToLines.count(Y)) return -1;
    vector<char> isTarget(M, 0);
    for (int t : stationToLines[Y]) isTarget[t] = 1;

    // 3) Dijkstra：进入新线路需支付该线路的price
    const long long INF = (long long)4e18;
    vector<long long> dist(M, INF);
    using P = pair<long long,int>;
    priority_queue<P, vector<P>, greater<P>> pq;

    for (int s : stationToLines[X]) {
        dist[s] = price[s];
        pq.emplace(dist[s], s);
    }

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        if (isTarget[u]) return d <= Z ? (int)d : -1;
        for (int v : adj[u]) {
            long long nd = d + price[v]; // 换乘到v，支付v票价
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.emplace(nd, v);
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int M, X, Y, Z;
    if (!(cin >> M >> X >> Y >> Z)) return 0;
    vector<int> price(M);
    vector<vector<int>> lineStations(M);
    for (int i = 0; i < M; ++i) {
        int p, n; cin >> p >> n;
        price[i] = p;
        lineStations[i].resize(n);
        for (int j = 0; j < n; ++j) cin >> lineStations[i][j];
    }
    int ans = min_cost(M, X, Y, Z, price, lineStations);
    cout << ans << "\n";
    return 0;
}

题目内容

为了方便城市居民有序流动，城市 $A$ 开通了一系列有轨电车路线，每列电车会沿固定的路线循环行驶，电车票价实行一票制，不论乘坐多少站，均按固定价格收费，循环坐车时不重复收费。请计算你在城市里面，从出发点到目的地，乘坐电车的最低费用。

输入描述

第 $1$ 行：$M$ $X$ $Y$ $Z$ ，其中：$M$ 代表电车线路总数量，$X$ 代表起点编号，$Y$ 代表终点编号，$Z$ 代表身上的金钱数。$1<=M<=50;0<=X,Y<=500;X丨=Y:1<=Z<=500$ 。输入以空格分隔。下面跟着 $M$ 行相同格式的数据。

第 $2$ 行：$price$ $n$ $station_1$ $station_2$ $station_3$ - $sation_n$ ，其中：$price$ 代表本条电车线路的票价，$n$ 代表本条电车路线经过的站点数量、后面跟着 $n$ 个数字，$station_1,station_2,station_3,...,station_n$ 代表本条电本线路经过的站点的站点编号，站点编号可能比站点总的数星大，$station_n$ 可能大于 $n$ 。$1<=n<=10,0<=station_n<=500;1<=price<=10$;

第 $M+1$ 行：$price$ $n$ $station_1$ $staton_2$ $sation_3$ ... $station_n$ 。

输出描述

需要花费的金钱数。如果无法达到或身上的金钱数不够达到，返回 $-1$ 。

样例1

输入

5 15 12 4
2 2 7 12
3 3 4 5 15
4 1 6
3 2 15 7
1 3 12 13 7

输出

4

说明

共 $5$ 条电车路线，要求从 $15$ 到 $12$，可选路线包括：

$a$：乘坐线路 $4(15->7)$ ，在 $7$ 站点换乘线路 $1(7->12)$

$b$ ：乘坐线路 $4(15->7)$ ，在 $7$ 站点换乘线路 $5(7->3->12->13)$

第二种乘坐方式花费更小，只需要 $4$

样例2

输入

2 1 6 5
2 3 1 2 7
3 3 3 6 7

输出

5

说明

从第一行输入可知，电车线路总数为 $2$ ，出发点编号为 $1$ ，终点编号为 $6$ ，身上的金钱数为 $5$ 。后面接着有 $2$ 行不定长数据。

从第二行输入可知，第一条电车路线的票价为 $2$ ，经过 $3$ 个站点，站点路线为 $[1,2,7]$ 。

从第三行输入可知，第二条电车路线的票价为 $3$ ，经过 $3$ 个站点，点路线为 $[3,6,7]$ 。

分析可得最优的乘坐策略是在 $1$ 站点先乘坐第一辆电车到达车站 $7$ ，然后换乘第二辆电车到车站 $6$ 。共花费金钱 $5$ ，没有超过身上的金钱数 $5$ ，故应返回结果 $5$ 。