标签: 最短路

「HDU 6290」奢侈的旅行

高玩小Q不仅喜欢玩寻宝游戏,还喜欢一款升级养成类游戏。在这个游戏的世界地图中一共有n个城镇,编号依次为1到n。

这些城镇之间有m条单向道路,第i 条单项道路包含四个参数ui,vi,ai,biui,vi,ai,bi,表示一条从ui号城镇出发,在vivi号城镇结束的单向道路,因为是单向道路,这不意味着小Q可以从vivi沿着该道路走到uiui。小Q的初始等级levellevel为1,每当试图经过一条道路时,需要支付cost=log2(level+ailevel)cost=log_2(\frac{level+a_i}{level})点积分,并且经过该道路后,小Q的等级会提升aiai级,到达level+ailevel+a_i级。但是每条道路都会在一定意义上歧视低消费玩家,准确地说,如果该次所需积分costbicost bi,那么小Q不能经过该次道路,也不能提升相应的等级。