最短路算法编程题：城市道路网络的最短路线

城市道路网络的最短路线

题目背景：

在一个城市里，有一个非常复杂的道路网络，其中不同的道路之间存在着不同的长度和速度限制，而每个路口都可以通向多个不同的道路。现在你需要编写一个程序，来求出从一个起点到达终点最短的路线。

编程要求：

请使用最短路算法来实现该程序。

具体的编程要求包括：

1. 输入数据格式：

   • 第一行包括两个整数，分别代表起点和终点的编号；
   • 第二行包括一个整数 n，代表总共有 n 条道路；
   • 接下来的 n 行，每行包括 3 个整数 a、b、c，表示从点 a 到点 b 的道路长度为 c。

2. 输出数据格式：

   • 输出从起点到终点的最短路线的长度。

注意事项：

• 若起点和终点之间无法到达，则输出 -1；
• 数据中可能存在负权边，需要考虑负权边的情况；
• 输入数据保证是合法且正确的，无需考虑输入数据的异常情况。

编程提示：

最短路算法可以使用 Dijkstra 算法或者 Bellman-Ford 算法来实现。其中，Dijkstra 算法适用于无负权边的情况，而 Bellman-Ford 算法则可以解决存在负权边的情况。在本题中，由于存在负权边，因此建议使用 Bellman-Ford 算法来实现。