P4224.第2题-转发下一跳问题
题目内容
网络中有 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
