去哪儿2018校招在线考试-编程题三

发表于 | 分类于 ，

题目 弃程的妙用

描述

一张机票的价格是由多个因素决定的，它通常与飞行距离没有直接的关系。
许多旅行者于是在这方面变得非常有创意，当飞机在多个城市停靠时，只是用机票的一部分，以实现低花费的旅行。
例如：
    北京到温哥华的机票可能卖8000元人民币，但是，北京-温哥华-西雅图的机票可能卖7500元，
    如果用户的目的地是温哥华，那么用户会选择买北京-温哥华-西雅图的机票，
    当他乘坐完北京-温哥华的航段后，会放弃乘坐温哥华到西雅图的航段。
然而，航空公司也了解这种行为，并通常要求一张机票所包含的站点必须要按顺序旅行，而且不允许中途加入其他路线。
例如：
    你手中有一张从北京到温哥华然后再到西雅图的机票，你不能仅使用机票中温哥华到西雅图的部分，
    你必须从机票上的第一个城市北京出发；
    此外，也不允许你从城市北京到城市温哥华，然后去一些其他地方如多伦多并返回温哥华，
    再继续你从温哥华到西雅图的旅途。
给出一组优惠的机票，以及一条或多条旅游路线，你要确定为了使旅行费用最少，应该如何购买机票。
现假设：优惠机票航线不多于10条，每组优惠机票的测试用例旅行路线不多于10条，
每张机票的航段数不多于5个，每个优惠航线票价不高于10000元

输入

包含一组测试用例，测试用例中描述一组优惠机票和一组旅行路线
每组测试用例由4部分组成：
第1行为优惠机票航线有多少条（n）
第2行~第2+n-1行描述优惠机票编号，每张优惠机票的价格、航段数和航段顺序
第2+n行描述了测试用例的旅行路线

输出

对于每条旅行路线，输出两行，包括路线的最小花费；
然后按使用顺序输出本次旅行所使用的机票编号，具体输出格式见样例，保证答案唯一。
如果输入参数不合法，则返回Error。

Example

Input

3
1 700 2 HongKong Seattle
2 700 3 Beijing Seattle Vancouver
3 1400 3 Beijing HongKong Vancouver
3 Beijing HongKong Seattle

Output

2100
3 1

题解

思路

  • 最短路径的变异题,每条边上有一个起点,一个终点,多个途经点
  • 由于给了路径,所以难度降低,Dijkstra 算法变形即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>

#define ll long long
using namespace std;

struct route
{
    int org;
    int fare;
    vector<int> des;
};
int n;
map<string,int>city;
vector<string>trip;
vector<int>tripC;
int minFare[15];
int passRoute[15];

void update(vector<route>&routes,int i)
{
    for(int j=0;j<n;++j)
    {
        if(routes[j].org==tripC[i])
        {
            int next=1;
            for(int k=0;k<routes[j].des.size();++k)
            {
                if(routes[j].des[k]==tripC[i+next])
                {
                    if(!minFare[i+next]||minFare[i+next]>minFare[i]+routes[j].fare)
                    {
                        minFare[i+next]=minFare[i]+routes[j].fare;
                        passRoute[i+next]=j+1;
                    }
                }
            }
        }
    }
}
void minDistance(vector<route>&routes)
{
    for(int i=0;i<tripC.size()-1;++i)
    {
        update(routes,i);
    }
}

int main()
{

    string tmp;
    int i,cIndex=0,tmpI,index,tFare;

    cin>>n;

    vector<route>routes(n);

    i=n;
    if(n>10)
    {
        cout<<"Error"<<endl;
        return 0;
    }

    while(i--)
    {
        cin>>index>>tFare>>tmpI>>tmp;
        if(tmpI>5)
        {
            cout<<"Error"<<endl;
            return 0;
        }
        if(!city.count(tmp))
            city[tmp]=cIndex++;
        routes[index-1].org=city[tmp];
        routes[index-1].fare=tFare;
        while(--tmpI)
        {
            cin>>tmp;
            if(!city.count(tmp))
                city[tmp]=cIndex++;
            routes[index-1].des.push_back(city[tmp]);
        }
    }

    cin>>tmpI;
    memset(minFare,0,sizeof minFare);
    memset(passRoute,0,sizeof passRoute);
    trip.clear();
    tripC.clear();

    while(tmpI--)
    {
        cin>>tmp;
        if(!city.count(tmp))
        {
            cout<<"Error"<<endl;
            return 0;
        }
        trip.push_back(tmp);
        tripC.push_back(city[tmp]);
    }

    minDistance(routes);

    if(minFare[tripC.size()-1])
    {
        cout<<minFare[tripC.size()-1]<<endl;
        int preRoute=0;
        for(int i=1;i<trip.size();++i)
        {
            if(passRoute[i]!=preRoute)
            {
                if(preRoute) cout<<" ";
                preRoute=passRoute[i];
                cout<<preRoute;
            }
        }
        cout<<endl;
    }
    else
    {
        cout<<"Error"<<endl;
    }
}