题目描述(ID:12255)
标题: 去网吧
标签: 动态规划
详情:
学校到网吧的路是错综复杂的,以致于到一个自己想去的网吧都有非常多的路线可以选择,而路线的长度又不相同,这样就决定了要花费的时间,因此想要尽快到达,选择一条最
佳的线路是很有必要的。
为了简化问题,我们把学校与周边的网吧看做图中的顶点,学校与网吧,网吧与网吧之
间的路线看做边,每个边都有一个权,表示我们走完这条路的时间,由于放学人流量大,如
果反向走会有危险,因此这是一个有向图。
我的的学校在 S点,想要去的网吧在 T点。你的任务就是选择一条最佳路线,使得从
学校到目的地网吧的时间最短,你只需要输出最短到达时间即可。
输入格式:
共有M+2 行数据
第一行两个整数 N,M,表示点数和边数。
然后M行每行3 个正整数(u,v,t),表示有一条可由u 到v耗时为 t的边。
最后一行两个正整数S、T。
输出格式:
只有一行,一个整数表示最短时间。如果 S、T之间不存在通路则输
出“No Solution!”(双引号不输出,“!”为西文标点)。
限制: 对于30%的数据保证有 1对于全部的数据保证有 1
样例:

输入

44
1 23
2 4 10
1 35
3 45
14

输出

10
登录并解答