BZPRO

#2395. [Balkan 2011]Timeismoney

内存限制：128 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

     有n个城市(编号从0..n-1)，m条公路(双向的)，从中选择n-1条边，使得任意的两个城市能够连通，一条边需要的c的费用和t的时间，定义一个方案的权值v=n-1条边的费用和*n-1条边的时间和，你的任务是求一个方案使得v最小

输入格式

第一行两个整数n,m,接下来每行四个整数a,b,c,t,表示有一条公路从城市a到城市b需要t时间和费用c

输出格式

【output】timeismoney.out
仅一行两个整数sumc，sumt,（sumc表示使得v最小时的费用和，sumc表示最小的时间和） 如果存在多个解使得sumc*sumt相等，输出sumc最小的

样例

样例输入


			
5 7

0 1 161 79

0 2 161 15

0 3 13 153

1 4 142 183

2 4 236 80

3 4 40 241

2 1 65 92

样例输出


			
279 501

数据范围与提示

【数据规模】

1<=N<=200

1<=m<=10000

0<=a,b<=n-1

0<=t,c<=255

有5%的数据m=n-1

有40%的数据有t=c

对于100%的数据如上所述

BZPRO Powered by Remmina.
Github Repository