题目描述(ID:12322)
标题: Artanis的路线规划
标签:
详情:
P城的路网可以看做是一张n个点的图。Artanis的学校在编号为1的点,家在编号为n的点。
每条道路由a,b,v,dis四个数值来描述,代表道路连接a和b两个点,长度为dis。如果v>0,代表道路是从a到b的单行线,如果逆行则需要被罚款v元。如果v=0,则代表道路不是单行线。
现在Artanis需要从学校回家,他的策略是首先尽量少被罚款,其次尽量走最短的距离。Artanis来问Zeratul该如何规划路线。但Zeratul正忙着出题没空理他,所以Zeratul把这个任务交给了你。
输入格式:
第一行包括两个整数n,m,代表点数和边数。
接下来m行,每行四个整数a,b,v,dis,含义见描述。
输出格式:
输出两个整数,代表最少的罚款金额,以及在罚款最少的情况下走的最短距离。
限制: 对于20%的数据,n<=100,m<=200
对于60%的数据,所有的v都为0,即所有的道路都不是单行线。
对于100%的数据,n<=100000,m<=200000,1<=a,b<=n,0<=v<=10^5,1<=dis<=10^5。数据保证Artanis可以从编号为1的点走到编号为n的点。
样例:

输入

5 5
1 2 0 5
2 3 0 10
3 4 0 15
4 5 0 20
5 1 1 20

输出

0 50

输入

5 5
1 2 0 5
2 3 0 10
3 4 0 15
5 4 1 20
5 1 1 20

输出

1 20
登录并解答