请高手帮忙——路径回溯
【问题描述】已知从起始点A到达各目站点(B、C、D...)的各最短路径上所有站点的前驱站点,以及至前驱站点的距离。以一个二维数组pre描述已知信息,第1列是前驱站点的序号(以0、1、2...分别表示站点A、B、C...),第2列是至前驱站点的距离。试推算和输出从起始点出发到达各其余站点的最短路径和距离。完成源程序DictS.CPP中Pathway函数的编写。
【输入】
输入文件DictS.in的第1行为1个自然数n(1<n<=26,表示包括起始点在内的站点总数);
后续n行,每行2个整数,分别描述站点A、B、C...的前驱站点和至前驱站点的距离。
【输出】
输出文件DictS.out包含n-1行,每行2个部分,前部为最短路径,后部为距离。格式见输出样例。
【输入输出样例1】
DictS.in DictS.out
9
0 0
0 40
0 20
4 10
0 30
2 25
3 10
2 40
6 20 A-B 40
A-C 20
A-E-D 40
A-E 30
A-C-F 45
A-E-D-G 50
A-C-H 60
A-E-D-G-I 70
【输入输出样例2】
DictS.in DictS.out
5
0 0
2 75
0 135
0 33
0 123 A-C-B 210
A-C 135
A-D 33
A-E 123