一个又想走快又贪的奸商。
使用 bfs 跑出最短路并且记录下路径并不难，学过算法的都会。。。
但是中间商赚差价，他想在路径最短的几条路上找出可以赚最大差价的一条。
解决方案
我们可以先跑一遍 bfs 得到最短的路径，这样第一个问题的答案我们就得到了（可以获得 20pts ）
现在我们可以将价值视为边权，使用动态转移 dp 设计。
f,g 表示从 点 1 到这个点的最大边权和最小边权，然后每转移一次就用 g_x - z 和 z - f_x 来分别更新答案。
输出的话就可以分别记录 f 和 g 的转移过程就可以了。