丝路驿站传信：最少换站次数与最短耗时路径 代码附录

• 完整解题档案：complete-solution-dossier.md

Python 主实现

源文件：main.py

• 实现状态：当前已有可执行实现

import heapq
import sys


def solve(data: str) -> str:
    tokens = list(map(int, data.split()))
    if not tokens:
        return ""
    it = iter(tokens)
    n = next(it)
    m = next(it)
    start = next(it)
    target = next(it)
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = next(it)
        v = next(it)
        days = next(it)
        graph[u].append((v, days))
        graph[v].append((u, days))
    inf = (10 ** 18, 10 ** 18)
    dist = [inf] * (n + 1)
    prev = [-1] * (n + 1)
    dist[start] = (0, 0)
    heap = [(0, 0, start)]
    while heap:
        steps, days, node = heapq.heappop(heap)
        if (steps, days) != dist[node]:
            continue
        for nxt, cost in graph[node]:
            cand = (steps + 1, days + cost)
            if cand < dist[nxt]:
                dist[nxt] = cand
                prev[nxt] = node
                heapq.heappush(heap, (cand[0], cand[1], nxt))
    if dist[target] == inf:
        return "relay_count=-1\ntotal_days=-1\npath=IMPOSSIBLE"
    path = []
    cur = target
    while cur != -1:
        path.append(cur)
        cur = prev[cur]
    path.reverse()
    return "\n".join(
        [
            f"relay_count={dist[target][0]}",
            f"total_days={dist[target][1]}",
            f"path={'->'.join(map(str, path))}",
        ]
    )


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")

C++ 对照实现

源文件：main.cpp

• 实现状态：当前已有可执行实现

#include <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <utility>
#include <vector>

using namespace std;

struct State {
    int steps;
    int days;
    int node;
    bool operator>(const State& other) const {
        if (steps != other.steps) {
            return steps > other.steps;
        }
        return days > other.days;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, start, target;
    if (!(cin >> n >> m >> start >> target)) {
        return 0;
    }
    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, days;
        cin >> u >> v >> days;
        graph[u].push_back({v, days});
        graph[v].push_back({u, days});
    }
    const pair<int, int> INF = {numeric_limits<int>::max() / 4, numeric_limits<int>::max() / 4};
    vector<pair<int, int>> dist(n + 1, INF);
    vector<int> prev(n + 1, -1);
    priority_queue<State, vector<State>, greater<State>> heap;
    dist[start] = {0, 0};
    heap.push({0, 0, start});
    while (!heap.empty()) {
        State cur = heap.top();
        heap.pop();
        if (make_pair(cur.steps, cur.days) != dist[cur.node]) {
            continue;
        }
        for (const auto& edge : graph[cur.node]) {
            int nxt = edge.first;
            int cand_steps = cur.steps + 1;
            int cand_days = cur.days + edge.second;
            pair<int, int> cand = {cand_steps, cand_days};
            if (cand < dist[nxt]) {
                dist[nxt] = cand;
                prev[nxt] = cur.node;
                heap.push({cand_steps, cand_days, nxt});
            }
        }
    }
    if (dist[target] == INF) {
        cout << "relay_count=-1\n";
        cout << "total_days=-1\n";
        cout << "path=IMPOSSIBLE\n";
        return 0;
    }
    vector<int> path;
    for (int cur = target; cur != -1; cur = prev[cur]) {
        path.push_back(cur);
    }
    reverse(path.begin(), path.end());
    cout << "relay_count=" << dist[target].first << "\n";
    cout << "total_days=" << dist[target].second << "\n";
    cout << "path=";
    for (size_t i = 0; i < path.size(); ++i) {
        if (i) {
            cout << "->";
        }
        cout << path[i];
    }
    cout << "\n";
    return 0;
}