A267.DJ舞池最强者---“斯特拉”

普及+/提高

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

青青草原每年都会有一场舞会,来让全员展现自己,表达自己。Gold King作为一份子,是积极参与的。舞会要求每一名舞者使用艺名,Gold King这一次打算用“斯特拉”这个艺名。为啥呢,因为跳舞需要消耗体力,舞姿设计又需要消耗脑力,为了达到最完美的状态,Gold King想用Dijkstra的方法消耗最少的精力。

舞会一开始有nn位舞者,分别依次站在编号为1,2,3...,n1,2,3,...,n的位置上,并且独自一人跳舞,过几分钟之后,舞者们会组成m组搭档,然后跳新舞曲,mm组搭档之间有各自的距离和体力消耗。

假设Gold King从ss号位置开始到tt号位置为止,中间每个位置上的舞者,Gold King会和她们共舞一曲(这个精力消耗是必须的,不算进体力消耗里面)。求解Gold King的最短距离和最少体力消耗的方案,如果最短距离有多条路线,则输出体力消耗最少的那条。

输入格式

输入有多组,每组数据如下:
第一行输入nnmm。表示有nn位舞者和mm组搭档。

然后输入mm行,每行44个数分别是a,b,d,pa,b,d,p。表示aabb之间有一条路,且距离为dd,体力消耗为pp

最后一行是两个数sstt,表示起点ss号位置,终点tt号位置。
当输入的nnmm00时输入结束。

输出格式

结果输出一行有两个数,分别是最短距离及其体力消耗。

输入输出样例

  • 输入#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

说明/提示

3n9003\le n\le 900
0<m<1000000<m<100000
s!=ts != t
10<d10<dp<1000p<1000

首页