PID341 / 星门跳跃
题目描述

在EVE游戏中,宇宙被划分成为许多区域,每个区域中都有数目不定的星门,可以通过星门来跳跃到特定的区域(星门是双向的)。

现在你正参与BBE联军与MLGBD联盟的会战,但由于飞船受损,需要尽快回到后方的友军空间站进行维护。

试编写程序,计算出所须的最短的返回空间站时间。

为了简化问题,我们约定飞船所在的位置为区域1,空间站所在的位置为区域N。

问题规模:

对于80%的数据,1<N<=10000,1<M<50000;

对于100%的数据,1<N<=30000,1<M<150000,1<=X[],Y[]<=N,1<=Z[]<=4096;

输入格式

第1行,两个整数N,M,分别为区域的总数和星门的总数;

第2..M+1行,每行三个整数X[i],Y[i],Z[i],分别为星门连接的两个区域,以及跳跃所需时间;

输出格式

一个整数,返回空间站所需的最短时间。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论