解题思路

• 问题抽象为：给定一个无向、正权图（路由器为点，链路代价为边权），求源路由器 s 到目的路由器 t 的最短路代价；同时给出当目的为 t 时，源路由器 s 的“下一跳集合”（即所有能出现在某条最短路径第一条边的相邻路由器）。

• 相关算法：Dijkstra 最短路算法（边权为正，适用）。

• 核心做法：

  1. 用邻接表存图，边为双向，权为 Lij。
  2. 分别从 s 与 t 各跑一次 Dijkstra，得到 distS[x] = s→x 的最短距离、distT[x] = x→t 的最短距离。
  3. 若 distS[t] 为无穷大（不可达），输出代价 -1 和下一跳 -1。
  4. 特判 s == t：代价 0，下一跳 -1。
  5. 否则，遍历 s 的所有邻居 v，若满足 w(s,v) + distT[v] == distS[t] 则 v 是某条最短路的第一跳，加入集合。最后按升序输出该集合（若集合为空，按题意输出 -1）。

• 上述判定的正确性：一条从 s 到 t 的最短路若以 s→v 开始，则整条路径长度等于首边权 w(s,v) 加上 v→t 的最短路长度 distT[v]，与全长 distS[t] 相等且最小。因此判定条件充要。

复杂度分析

• 设路由器数 n、链路数 k。一次 Dijkstra 复杂度为 O((n + k) log n)（优先队列 + 邻接表），两次仍为 O((n + k) log n)。
• 空间复杂度 O(n + k)（存图与两个距离数组）。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意：无向正权图，求 s 到 t 的最短路代价与从 s 出发的下一跳集合
# 思路：两次 Dijkstra（从 s 和从 t），用 distS、distT 判定下一跳

import sys
import heapq

INF = 10 ** 18

def dijkstra(n, graph, start):
    """从 start 出发的 Dijkstra，返回最短距离数组"""
    dist = [INF] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]  # (距离, 节点)
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

def solve():
    data = list(map(int, sys.stdin.read().split()))
    it = iter(data)
    n = next(it); k = next(it)

    # 邻接表
    g = [[] for _ in range(n + 1)]
    # 记录 s 的邻居需要权重，可直接从 g[s] 中取
    for _ in range(k):
        u = next(it); v = next(it); w = next(it)
        g[u].append((v, w))
        g[v].append((u, w))
    s = next(it); t = next(it)

    if s == t:
        print(0)
        print(-1)
        return

    distS = dijkstra(n, g, s)
    distT = dijkstra(n, g, t)

    if distS[t] >= INF:
        print(-1)
        print(-1)
        return

    # 判定下一跳：所有满足 w(s,v) + distT[v] == distS[t] 的邻居 v
    hops = []
    for v, w in g[s]:
        if w + distT[v] == distS[t]:
            hops.append(v)
    hops = sorted(set(hops))  # 去重并升序

    print(distS[t])
    if hops:
        print(" ".join(map(str, hops)))
    else:
        print(-1)

if __name__ == "__main__":
    solve()

Java

// 题意：无向正权图，求 s->t 最短路代价与 s 的下一跳集合
// 思路：从 s、t 分别跑 Dijkstra；根据 w(s,v)+distT[v]==distS[t] 判定下一跳
import java.io.*;
import java.util.*;

public class Main {
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    static class Edge {
        int to, w;
        Edge(int t, int w) { this.to = t; this.w = w; }
    }

    static long[] dijkstra(int n, List<Edge>[] g, int s) {
        long INF = Long.MAX_VALUE / 4;
        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        dist[s] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.add(new long[]{0, s});
        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long d = cur[0];
            int u = (int) cur[1];
            if (d != dist[u]) continue;
            for (Edge e : g[u]) {
                int v = e.to;
                long nd = d + e.w;
                if (nd < dist[v]) {
                    dist[v] = nd;
                    pq.add(new long[]{nd, v});
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);

        int n = fs.nextInt();
        int k = fs.nextInt();

        @SuppressWarnings("unchecked")
        List<Edge>[] g = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) g[i] = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            int u = fs.nextInt();
            int v = fs.nextInt();
            int w = fs.nextInt();
            g[u].add(new Edge(v, w));
            g[v].add(new Edge(u, w));
        }
        int s = fs.nextInt();
        int t = fs.nextInt();

        if (s == t) {
            System.out.println(0);
            System.out.println(-1);
            return;
        }

        long[] distS = dijkstra(n, g, s);
        long[] distT = dijkstra(n, g, t);
        long INF = Long.MAX_VALUE / 4;

        if (distS[t] >= INF) {
            System.out.println(-1);
            System.out.println(-1);
            return;
        }

        // 检查 s 的所有邻居
        TreeSet<Integer> hops = new TreeSet<>();
        for (Edge e : g[s]) {
            int v = e.to;
            if (e.w + distT[v] == distS[t]) {
                hops.add(v);
            }
        }

        System.out.println(distS[t]);
        if (hops.isEmpty()) {
            System.out.println(-1);
        } else {
            StringBuilder sb = new StringBuilder();
            boolean first = true;
            for (int v : hops) {
                if (!first) sb.append(' ');
                first = false;
                sb.append(v);
            }
            System.out.println(sb.toString());
        }
    }
}

C++

// 题意：无向正权图，求 s->t 最短路代价与 s 的下一跳集合
// 思路：两次 Dijkstra；判定条件 w(s,v)+distT[v]==distS[t]
#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL<<62);

struct Edge {
    int to, w;
};
vector<vector<Edge>> g;

vector<long long> dijkstra(int n, int s) {
    vector<long long> dist(n + 1, INF);
    dist[s] = 0;
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto &e : g[u]) {
            int v = e.to;
            long long nd = d + e.w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push({nd, v});
            }
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;

    g.assign(n + 1, {});
    for (int i = 0; i < k; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    int s, t;
    cin >> s >> t;

    if (s == t) {
        cout << 0 << "\n" << -1 << "\n";
        return 0;
    }

    auto distS = dijkstra(n, s);
    auto distT = dijkstra(n, t);

    if (distS[t] >= INF/2) {
        cout << -1 << "\n" << -1 << "\n";
        return 0;
    }

    // 判定 s 的下一跳
    set<int> hops; // 用 set 保证升序且去重
    for (auto &e : g[s]) {
        int v = e.to;
        if ((long long)e.w + distT[v] == distS[t]) {
            hops.insert(v);
        }
    }

    cout << distS[t] << "\n";
    if (hops.empty()) {
        cout << -1 << "\n";
    } else {
        bool first = true;
        for (int v : hops) {
            if (!first) cout << ' ';
            first = false;
            cout << v;
        }
        cout << "\n";
    }
    return 0;
}

题目内容

网络中有 $n$ 台路由器 $R1,R2,...,Rn$，两台路由器之间最多只有一条链路双向连通，每条链路有对应的转发成 本 $Lij(Lij>0,Lij=Lji)$ 。以 $Ri$ 为源节点进行转发时，会以 $Ri$ 为根基于链路转发成本计算一棵最短路径树，$Ri$ 到其它 $Rj$ 的报文会沿着最短路径树进行转发。以下图拓扑为例，$R1$ 到 $R2$ 的最短路径为 $R1->R2$ ，最小转发代价为 $5$ (所有路径成本之和).

转发的下一跳定义如下: 源节点 $S$ 到目的节点 $D$ 的最短路径上 $S$ 的直连的邻居节点，用来指导报文从哪条链路转发。以下图为例，$R1$ 到 $R2$ 的转发下一跳为 $R2$ 。

需要注意的是，最短路径树中最短路径可能不止一条，对应转发的下一跳可能存在多个。以下图为例，$R1$ 到 $R3$ 的最短路径有两条,分别为: $R1->R2->R3;R1->R4->R3$,$R1$ 到 $R3$ 的转发下一跳为 $R2、R4$ 。

任务:给定路由器数量和路由器之间的连通关系及转发成本，并指定两个路由器 $Ri、Rj$ ，计算以 $Rj$ 为目的时， $Ri$ 到 $Rj$ 的最小转发代价，以及 $Ri$ 的转发下一跳的集合。

输入描述

第 $1$ 行包含两个整数，分别表示路由器个数 $n$ 、连通关系个数 $k,1<=n<=1000,1<=k<=n*(n-1)/2$

第 $2$ 行开始的 $k$ 行代表链路信息,每行 $3$ 个正整数:路由器 $Ri$ 、路由器 $Rj$ 、链路转发成本 $Lij$ ，$1<=Lij<=100$，$Ri、Rj$ 在 $[1,n]$ 范围内

最后一行包含 $2$ 个正整数，为源路由器 $Ri$ ，以及目的路由器 $Rj$ 。

输出描述

输出包括两行:

第一行为 $Ri$ 到 $Rj$ 之间的最小转发代价

第二行为一个正整数序列，以单个空格间隔,表示以 $Rj$ 为目的时，$Ri$ 的转发下一跳集合，要求升序排列。

注：

1.若两个路由器之间未连通，则最小转发代价为 $1$ ，转发下一跳集合为 $-1$

2.若源节点和目的节点为同一个点，最小转发代价为 $0$ ，转发下一跳集合为 $-1$

样例1

输入

4 3
1 2 5
1 3 5
2 3 5
1 4

输出

-1
-1

说明

$1$ 作为源路由器，$4$ 作为目的路由，$1->4$ 路径不可达，最小转发代价为 $-1$ ，转发下一跳集合为空

样例2

输入

4 4
1 2 5
2 3 5
3 4 5
1 4 5
1 3

输出

10
2 4

说明

$1$ 作为源路由器，$3$ 作为目的路由器，$1->3$ 的最短路径为 $1->2->3$ 和 $1->4->3$ ，最小转发代价为$10$ ，转发下一跳集合为 $24$

样例3

输入

4 4
1 2 5
2 3 5
3 4 5
1 4 10
1 3

输出

10
2

说明

$1$ 作为源路由器，$3$ 作为目的路由器，$1->3$ 的最短路径为 $1->2->3$ , 最小转发代价为 $10$ 。转发下一跳仅 有 $2$