解题思路

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

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

• 核心做法：

  1. 用邻接表存图，边为双向，权为 Lij。
  2. 分别从 s 与 t 各跑一次 Dijkstra，得到 distS[x] = s→x 的最短距离、distT[x] = x→t 的最短距离。
  3. 若 distS[t] 为无穷大（不可达），输出代价 -1 和下一跳 -1。

题目内容

网络中有 $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$