题目描述(ID:12185)
标题: 一起去郊游
标签: 图结构 最短路 网络流
详情: 小哼和同学一起在泰国旅游,他们的宾馆处于1号站点,需要坐车去第n号站点游玩。站点之间可以乘坐交通工具,但是每两个站点之间的交通工具都不同,有的是tutu车最多只能同时坐3个人,每个人的车费是10元;有的站点之间是双条车最多同时可以做10个人,每个人的车费是2元。现在请问从1号站点出发,最多可以有多少人可以到达n号站点,并且总费用最低是多少?
输入格式:
第一行包含2个正整数N、M分别表示站点的个数、以及有向边的个数N (0 <= N <= 200) 和 M (2 <= M <= 200)
接下来M行每行包含四个正整数u、v、w、f,表示第i条有向边从u出发,到达v,可以同时做w个人,每个人的乘车费用是f。(0 <= w <= 1000000 , 1<= f <= 10)
输出格式:
一行,包含两个整数,依次为最多可以有多少人可以到达n号占站点,最小费用是多少?
样例:

输入

4 5
1 2 30 2
1 4 20 3
2 4 20 1
2 3 30 9
3 4 40 5

输出

50 280

输入

6 10
1 3 4 7
1 2 3 1
2 5 4 5
2 4 6 4
2 3 1 1
3 5 3 6
3 4 5 3
4 6 7 6
5 6 3 2
5 4 3 3

输出

7 88

解释

v1-v2 3*1
v1-v3 4*7
v2-v5 3*5
v3-v4 4*3
v4-v6 4*6
v5-v6 3*2
3*1+4*7+3*5+4*3+4*6+3*2=88
登录并解答