游戏厅的路

Grade 100 Open Time Wednesday, 17 June 2020, 8:50 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 8:50 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 8:50 PM
Input file game.in Output file game.out

【题目描述】游戏厅的路(game)

  学院附近出现了众多的游戏厅,但是由于学院的学员众多(≤3 000),所以抢到游戏机玩的难度非常之大。学院到游戏厅的路是错综复杂的,以至于到一个自己想去的游戏厅都有非常多的路线可以选择,而路线的长度又不相同,因此想要尽快到达,选择一条最佳的线路是很有必要的。

  为了简化问题,我们把学院与周边的游戏厅看做图中的顶点,学校与游戏厅,游戏厅与游戏厅之间的路线看做边,每个边都有一个权,表示我们走完这条路的时间,由于放学人流量大,如果反向走会有危险,因此这是一个有向图。设学院在 S点,想要去的游戏厅在 T点。你的任务就是选择一条最佳路线,使得从学校到目的地游戏厅的时间最短,你只需要输出最短到达时间即可。

  【输入格式】

  输入共有M+2 行数据,第一行两个整数 N,M,表示点数和边数。

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

  【输出格式】

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

  【输入样例】

  4 4

  1 2 3

  2 4 10

  1 3 5

  3 4 5

  1 4

  【输出样例】

  10

  【数据规模】

  对于全部的数据保证有 1<N≤1 000,1≤M≤1 000;