USACO 2015 January Contest Bronze——奶牛的旅行路线

题目描述

厌倦了农场寒冷的冬季天气，奶牛贝茜计划飞往一个温暖的目的地度假。

不幸的是，她发现只有一家航空公司，博维尼亚航空，愿意向奶牛出售机票，而且这些机票的结构有些复杂。

博维尼亚航空公司拥有 N 架飞机，每架飞机都在由两个或多个城市组成的特定“航线”上飞行。

例如，一架飞机可能从城市 1 起飞，然后飞到城市 5，然后飞到城市 2，最后飞到城市 8。

没有一个城市会在一条航线上出现多次。

如果贝茜选择了一条航线，那么她可以在航线上的任何城市登机，然后在航线上的任何城市下飞机。

她不需要在航线的第一个城市登机或在最后一个城市下机。

每条航线都有一定的费用，只要贝茜乘坐了某个航线，不论乘坐时途径的城市有多少，都需要支付全部的航线费用。

贝茜想找到从她所在的农场（在 A 市）到热带目的地（B 市）的最便宜的旅行方式。

奶牛只想走一条路线

请确定她需要支付的最低费用。

输入格式

第一行包含三个整数 A,B,N。

接下来 2N 行，每两行描述一条航线，第一行包含航线的乘坐费用以及航线途径的城市数量。第二行包含按航线顺序排列的城市列表。

输出格式

输出贝茜从 A 到 B 所需要支付的最低费用。

如果无法到达目的地，则输出 −1。

数据范围

1≤N≤500,
1≤ 航线费用 ≤1000,
1≤ 航线途径城市数量 ≤500,
城市编号范围 [1,10000]。

输入样例

1 2 3
3 3
3 2 1
4 4
2 1 4 3
8 5
4 1 7 8 2

输出样例

7

实现代码——奶牛只想走一条路线的情况下

#include <iostream>
using namespace std;

int main() {
    int start,end,line_num;
    cin>>start>>end>>line_num;
    int all_consume = -1;
    for(int i = 0;i < line_num;i ++){

        //获取费用和城市的数量
        int fare,city_num;
        cin>>fare>>city_num;
        bool flag = false;

        //遍历没有给输入
        for(int j = 0;j < city_num;j ++){
            int temp;
            cin>>temp;

            //判定如果存在start城市，打开flag进行第二次判定
            if(temp == start){
                flag = true;
            }

            //如果已经确认存在start，就判定是否存在end
            if(temp == end && flag){
                if(all_consume == -1){
                    all_consume = fare;
                }else{
                    all_consume = (all_consume > fare)?fare:all_consume;
                }
            }
        }
    }
    cout<<all_consume;

}