#P1854. 【算法】【20】DJ舞池最强者---“斯特拉”

【算法】【20】DJ舞池最强者---“斯特拉”

问题说明

青青草原每年都会有一场舞会,来让全员展现自己,表达自己。Gold King作为一份子,是积极参与的。舞会要求每一名舞者使用艺名,Gold King这一次打算用“斯特拉”这个艺名。为啥呢,因为跳舞需要消耗体力,舞姿设计又需要消耗脑力,为了达到最完美的状态,Gold King想用Dijkstra的方法消耗最少的精力。
舞会一开始有n位舞者,分别依次站在编号为1,2,3,...,n的位置上,并且独自一人跳舞,过几分钟之后,舞者们会组成m组搭档,然后跳新舞曲,m组搭档之间有各自的距离和体力消耗。假设Gold King从s号位置开始到t号位置为止,中间每个位置上的舞者,Gold King会和她们共舞一曲(这个精力消耗是必须的,不算进体力消耗里面)。求解Gold King的最短距离和最少体力消耗的方案,如果最短距离有多条路线,则输出体力消耗最少的那条。

输入格式

输入有多组,每组数据如下:
第一行输入n和m。表示有n位舞者和m组搭档。
然后输入m行,每行4个数分别是a,b,d,p。表示a和b之间有一条路,且距离为d,体力消耗为p。
最后一行是两个数s和t,表示起点s号位置,终点t号位置。
当输入的n和m为0时输入结束。


输出格式

结果输出一行有两个数,分别是最短距离及其体力消耗。
样例1输入:
3 2
1 2 5 6
2 3 4 5
1 3
0 0
样例2输入:
6 12
6 2 18 10
2 4 17 11
5 1 16 14
6 6 16 17
6 5 15 13
6 2 18 10
3 5 14 18
1 3 18 18
2 6 11 18
3 4 16 17
1 6 18 13
5 6 10 18
2 4
0 0
样例1输出:
9 11
样例2输出:
17 11

提示

3<=n<=900
0<m<100000
s != t
10<d,p<1000


来源/分类

算法培训-20-最短路径