← 返回题目
题库练习 DJ舞池最强者---“斯特拉”
← 上一题 下一题 →

A356 | DJ舞池最强者---“斯特拉”

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

青青草原每年都会有一场舞会，来让全员展现自己，表达自己。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
输出 #1
9 11
输入 #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
输出 #2
17 11
C++ 编辑器
输入
输出