求简单有向带权图中两个顶点间的最短路径算法
圣诞岛的旅行ProblemAngel最近无聊,去了圣诞岛(CX *^_^*),他喜欢无目的的乱逛,当然,他不会轻易地回头。Angel想去广场,那么,他什么时候才能到呢?你已经得到了CX的地图,地图上有N(N <= 100)个交叉路口,交叉路口之间有马路相连接(不超过1000条马路)。因为CX的人遵循奇怪的规则,道路都是单向的,不同的道路之间有一定的距离,我们假设Angel所在的地点为点1,广场所在点为N。假设Angel走一单位距离需要一单位时间。问Angel最早和最迟什么时候到达广场?
Input
本题有多组数据,第一行N, M,M是边的数量以后M行,每行3个整数X, Y, Weight,代表一条从X城市到Y城市,长度为Wweight的边。
Output
每组数据,第一行是最少时间,第二行是最迟时间,要是可怜的Angel可能永远到不了广场,输出一行Never。
求这题的算法?