Problem 1: Cow Routing [Richard Peng, 2015]
Tired of the cold winter weather on her farm, Bessie the cow plans to
fly to a warmer destination for vacation.she
discovers that only one airline, Air Bovinia, is willing to sell
tickets to cows, and that these tickets are somewhat complicated in
structure.
Air Bovinia owns N planes (1 <= N <= 500), each of which flies on a
specific "route" consisting of two or more cities. For example, one
plane might fly on a route that starts at city 1, then flies to city
5, then flies to city 2, and then finally flies to city 8. No city
appears multiple times in a route. If Bessie chooses to utilize a
route, she can board at any city along the route and then disembark at
any city later along the route. She does not need to board at the
first city or disembark at the last city. Each route has a certain
cost, which Bessie must pay if she uses any part of the route,
irrespective of the number of cities she visits along the route.
Bessie would like to find the cheapest way to travel from her farm
(in city A) to her tropical destination (city B). Since she does not
want to be confused by a complicated itinerary, she wants to use only
a single route. Please help her decide what is the minimum cost she
must pay.
牛贝西（Bessie）厌倦了她的农场寒冷的冬天天气，牛计划飞往一个温暖的目的地休假。她发现只有一家航空公司Air Bovinia愿意向母牛出售门票，并且这些门票的结构有些复杂。 Air Bovinia拥有n个平面（1 <= n
<= 500），每个平面都在由两个或更多城市组成的特定“路线”上飞行。例如，一架飞机可能会在一条从城市1开始的路线上飞行，然后飞往5号城市，然后飞往城市2，然后终于飞往城市8。任何城市都没有多次出现在一条路线中。如果贝西选择使用一条路线，她可以在路线沿途的任何城市登机，然后在后来沿途的任何城市下车。她不需要在第一个城市登机，也不需要在最后一个城市下船。每条路线都有一定的费用，如果贝西使用路线的任何部分，就必须支付，而与她沿着路线访问的城市数量无关。贝西想找到一种从她的农场（在A城市）到她的热带目的地（城市B）的最便宜的方式。由于她不想被复杂的行程混淆，因此她只想使用一条路线。请帮助她确定她必须支付的最低费用是多少。