关于用Dijksra算法求最短路_乐园游览车 算法

Dijksra是图论中的一种最基础的算法，但之前我对其理解有偏差，直到今天才纠正过来。

首先Dijksra是一种基于贪心的算法，可以求解最短路问题，但不能用于对于负全边的计算上。其思想简单来说就是将将所有地点分为s（已确定到起点最短路）和p（未确定）两个集合，通过n次迭代，每次从p中找到最短路径t来，并将t加入s中，从而确定最短距离。例如

蒜头君来到一个巨大的游乐场，这里有 n个景点。景点和景点之间不能步行，只能乘坐指定的游览车。游览车的数量是无限的，只要你想乘坐就能瞬间出发。现在有 m 种类型的游览车，每种游览车只能在固定的两个景点 u 和 v 之间来回运作，每一趟消耗的时间为 w。蒜头君现在在 1 号景点，他想去 n号景点，请你计算最短需要花费多少时间。

输入格式

第一行两个整数 n,m (1<= n <= 2500,1<= m <= 10^5)分别表示景点数量和游览车数量。

接下来 m 行，每行三个整数 u,v,w (1≤u,v≤n,1≤w≤105,u!=v)，表示每种游览车连接的两个景点，和一趟运输所需的时间。

输出格式

输出一个整数，表示最短的时间。如果无法到达 n 号景点，输出 -1。

Sample 1

Input	Output
5 8 1 2 3 2 3 4 3 4 5 4 5 6 1 3 4 2 4 7 2 5 8 1 5 100	11