/ Vijos / 题库 /

尾声-怪盗基德的逃离

尾声-怪盗基德的逃离

背景

怪盗基德第四次拿着战利品信心满满地离开了OIBH总部,一路上大摇大摆,好不
嚣张。OIBH的人看不下去又没办法,打算作罢,可是有一天……
当当当当……当OIBH总部的吃饭铃声响起的时候,所有正在埋头工作的大牛们都
以迅雷不及掩耳盗铃之势向食堂冲去。食堂的大门顿时被人群塞的鼓鼓的(可怜
ing...)
当大牛们正在全力消灭由水稻演变而来的那东西时,突然走进来一个玉树临风英
俊潇洒人见人爱花见花开啤酒见啤酒盖开的大帅哥(啊啊啊啊啊啊啊啊啊啊……),
而他自称是一个超超超级大牛!!
超超超级大牛在听说了怪盗基德的事情后,二话不说,提笔“刷刷”的写了一页
纸,其余大牛们研究了九天九夜,终于明白了纸上写的是什么,那是一个(咳咳)
专门对付怪盗基德的陷阱!
而怪盗基德在毫不知情的情况下,竟然把四块宝石都送回了OIBH总部,还留下预
告函,将向第五块宝石发起攻势!
大牛们气愤而又坏笑着,悄悄地设下了陷阱……
结果出乎所有人的意料,宝石还是被拿走了,可是,为什么大牛们还在阴笑……
难不成,他们在怪盗基德逃离的路上设下了陷阱?

描述

果然,基德的撤退路上被布置一个巨大的迷宫。这迷宫是一个巨大的道路网,每
条路上基德需要花费的时间都不同,而每条路都需要不同的过路费。这个道路网
可以看做一个无向图,其中共有n个结点,共m对结点间有通路。1号结点是入口,
n号结点是出口。现在要求你在规定时间内,花去尽可能多的钱(据说不这样做就
不是基德的性格)帮助基德走过迷宫。注意:每条路只能走一次,走到终点即结
束而不能往回走。在钱数相同的情况下使时间尽量短。

格式

输入格式

第一行4个整数n,m,t,v,分别是结点总数,通路总数,规定时间,及基德所拥有
的钱。接下去m行,每行4个整数a,b,c,d,a和b表示有通路的两结点,c为此路费
时,d代表此路过路费。

输出格式

输出共2个整数t2,v2,分别表示用时和所剩钱数。你要保证t2<=t且v2>=0。

样例1

样例输入1

8 10 10 120
1 2 2 1
1 3 1 1
1 4 2 19
2 3 2 6
3 4 1 1
3 5 2 2
5 6 2 1
6 7 1 3
7 8 3 1
4 8 7 100

样例输出1

9 1

限制

每个点1s

提示

2<=n<=100
1<=t,v<=500
样例说明
道路网如图所示【道路上括号外为费时,括号内为过路费】
1->4->8即为所求路径,用时为9,费钱为119。

来源

From 玛维-影之歌
这不再是水题...
感谢 宇智波带狗 提供标程
感谢 kaito&aoko 提供背景

信息

ID
1399
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
790
已通过
242
通过率
31%
被复制
1
上传者

相关

在下列训练计划中:

RP++分类题库