与无向图最短路径有关

问题:一个无向图有n个点,m条边,你现在在1号点,每条边有个对能力值的限制,要大于等于这个限制才能通过它。他们想知道他们至少要有多大的能力值,才能从1号点到n号点。

输入:第一行两个正整数n,m。分别表示图的大小和边的数量。
接下来m行,每行3个整数 u,v,l 。表示有一条u到v的边,至少要l能力值才能通过。地图保证1和n是连通的。

数据规模:对于30%的数据: n<=m<=8
对于100%的数据 , n<=m<=10^6,1<=u,v<=n,0<=l<=10^9

输出描述:需要获得的最小的能力值,能够从1到n

我的想法和出现的问题:我本来打算先求最短路径的,再找出最短路径上最长的一条边的值,但是它测试数据太大了,我邻接矩阵一开数组就爆栈了。有没有什么不爆数组的思路啊。

最短路径不对,路径最短不代表它是由最短的边组成的
比如最短的路径是1,100,第二短的路径是102条长度为1的路径组成,很显然最短路径跟这题完全不是同一个问题
而且求最短路径你需要验证每个路径,很耗费时间
这题其实最适合用贪心算法求,反正每路过一个节点,你都走最短的那条就对了