最优路线问题(Best Route)

题目描述

给定一张 n 个顶点、m 条边的无向带权图，顶点编号为 1~n。每条边有一个路途花费。现在需要从地图中寻找从起点 1 到终点 n 的最优路线，最优路线是指路途花费总和最小的路线。

输入格式

第一行两个整数 n 和 m。

接下来 m 行，每行三个整数 u、v、w，表示顶点 u 和顶点 v 之间有一条花费为 w 的无向边。图中可能存在重边。

输出格式

一个整数，表示从顶点 1 到顶点 n 的最小花费。数据保证存在通路。

样例输入

5 8
1 2 10
1 5 50
2 3 15
2 5 35
3 1 25
3 4 10
4 5 20
5 3 20

样例输出

45

样例说明：从顶点 1 出发，走 1 → 2 → 3 → 4 → 5，总花费为 10 + 15 + 10 + 20 = 45，这是所有路线中花费最小的。

数据范围

• n ≤ 15，m ≤ 100；
• 1 ≤ w ≤ 1000；
• 图为无向图，可能存在重边；
• 数据保证从顶点 1 到顶点 n 存在通路。