UVA1048 Low Cost Air Travel

题意翻译： 很多航空公司都会出售一种联票，要求从头坐，上飞机时上缴机票，可以在中途任何一站下飞机。比如，假设你有一张“城市$1$->城市$2$->城市$3$”的联票，你不能用来只从城市$2$飞到城市$3$（因为必须从头坐），也不能先从城市$1$飞到城市$2$再用其他票飞到其他城市玩，回到城市$2$后再用原来的机票飞到城市$3$（因为机票已经上缴）。 这里有一个例子。假设有3种票，每种票的情况如下所示： - 票1：城市$1$->城市$3$->城市$4$，票价$225$美元 - 票2：城市$1$->城市$2$，票价$200$美元 - 票3：城市$2$->城市$3$，票价$50$美元 你想从城市$1$飞到城市$3$，有两种方法可以选择。买票$1$，只飞第一段；买票$2$和$3$，通过城市$2$中转。显然，第一种方法比较省钱，虽然浪费了一段。 给出票的信息，以及一个或多个行程单，你的任务是买尽量少的票（同一种票可以买多张），使得总花费最小。输入保证行程总是可行的。行程单上的城市必须按顺序到达，但中间可以经过一些辅助城市。

无

无