问题 5373 --AimNetbar -训练套题T17T3

5373: AimNetbar -训练套题T17T3

时间限制: 1 Sec  内存限制: 512 MB
提交: 75  解决: 15
[提交][状态][讨论版][命题人:]

题目描述

3. AimNetbar  (netbar.pas/in/out)


【问题描述】

  我们把学校与周边的网吧看做图中的顶点,学校与网吧,网吧与网吧之 间的路线看做边,每个边都有一个权,表示我们走完这条路的时间,由于放学人流量大,如 果反向走会有危险,因此这是一个有向图。

我的的学校在 S 点,想要去的网吧在 T 点。你的任务就是选择一条最佳路线,使得从学校到目的地网吧的时间最短,你只需要输出最短到达时间即可。

【输入文件】

netbar.in 中共有 M+2 行数据

第一行两个整数  NM,表示点数和边数。

然后 M 行每行 3 个正整数(uvt),表示有一条可由 u v 耗时为 t 的边。

最后一行两个正整数 ST

【输出文件】

netbar.out 中,只有一行,一个整数表示最短时间。如果 ST 之间不存在通路则输 出“No Solution!”(双引号不输出,“!”为西文标点)

【输入样例】

4 4

1 2 3

2 4 10

1 3 5

3 4 5

1 4

【输出样例】

10

【数据规模】

对于 30%的数据保证有  1<N<=10001<=M<=1000

对于全部的数据保证有  1<N<=100001<=M<=100000

来源

 

[提交][状态]