蓝桥杯2019年第十届省赛真题-空间跳跃

在游戏《星际争霸 II》中，战列巡航舰作为人类的终极作战武器，在后期 以及一些中期战术中发挥着空中堡垒的作用，其 “战术跳跃” 技能能让其在游戏 中期在敌军基地上空造成打击之后在血量较低时撤离，进行无战损骚扰，在人 类 vs 异虫对抗中经常用来压制异虫中期的发展。

你在玩一个游戏，游戏中有 n 个地点和 m 条单向时空航道。每条时空航道形如 (u, v, w, x)，其中 u，v 表示这条时空航道的起点终点，w 表示通过这条航道需要的时间(注意这个时间是现实当中游戏者的时间也是游戏内的时间)，x表示这条航道使用的频繁程度。时空航道不会成环，但可能会有两条航道的起别为x ,x ,x ,···x，那么选择第i个航道的概率就是∑ xi 。你的目的是在L 123 k kj=1xj点相同同时终点也相同。游戏开始的时候，你的战列巡航舰到达了地点 1，每当你到达一个地点的时候，战舰的电脑会按照每个起点为该地点的时空航道的频繁程度随机选择一个航道并花费 w 单位时间到达该航道的终点。具体来说，对于一个时间点 u，假如有 k 个起点为该地点的时空航道，他们的频繁程度分别为x ,x ,x ,···x，那么选择第i个航道的概率就是∑ xi 。你的目的是在L 123 k kj=1xj单位游戏时间内到达一个没有任何以该地点为起点的时空航道的地点。当然你 可以在到达某一个地点时重新开始游戏，如果你重新开始这个游戏，你就能回 到游戏开始的那一刻(即 1 号地点)并重置游戏内的时间(即你又可以有 L 单 位的时间去跳跃了)，你也可以在没有任何以该地点为起点的地点重新开始，且 无次数限制。你需要最小化你在现实中花费的时间。当然在你运气足够好的情 况下，你一定可以达成游戏目标。