andyli

题解 UVA1048 【Low Cost Air Travel】
题意翻译很多航空公司都会出售一种联票,要求从头坐,上飞机时上缴机票,可以在中途任何一站下飞机。比如,假设你有一张“...
扫描右侧二维码阅读全文
03
2019/07

题解 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$中转。显然,第一种方法比较省钱,虽然浪费了一段。
给出票的信息,以及一个或多个行程单,你的任务是买尽量少的票(同一种票可以买多张),使得总花费最小。输入保证行程总是可行的。行程单上的城市必须按顺序到达,但中间可以经过一些辅助城市。

输入格式

输入包含多组数据。每组数据第一行为一个整数$NT$,即联票的种类数。以下$NT$行每行为一个联票描述,其中第一个整数为票的价格,然后是联票上城市的数目以及这些城市的整数编号(按顺序给出)。接下来为一个整数$NI$,即需要计算最小花费的行程单数目。以下$NI$行每行为一个行程单,其中一个整数为行程单上的城市数目(包括起始城市),以及这些城市的编号(按顺序给出)。输入保证每组数据最多包含$20$种联票和$20$个行程单,每张票或者行程单上有至少$2$个,最多$10$个城市。票价不超过$\$ 10000$。联票或者行程单上的相邻城市保证不同。票和行程单都从$1$开始编号。输入结束标志为$NT=0$。

输出格式

对于每组数据的每张行程单,输出最小花费和对应的方案(按顺序,详见样例输出)。输出保证唯一。

样例输入

3
225 3 1 3 4
200 2 1 2
50 2 2 3
1
2 1 3
3
100 2 2 4
100 3 1 4 3
200 3 1 2 3
2
3 1 4 3
3 1 2 4
0

样例输出

Case 1, Trip 1: Cost = 225
  Tickets used: 1
Case 2, Trip 1: Cost = 100
  Tickets used: 2
Case 2, Trip 2: Cost = 300
  Tickets used: 3 1

要依次经过行程单上的各个城市,那么是不是可以先求出每两个相邻城市的最小花费,再加起来呢?不可以,因为不一定每两个相邻城市都是用一张或多张完整的票。比如行程单上是城市$1$->城市$2$->城市$3$,只有一张票:城市$1$->城市$2$->城市$3$。在这样的情况下,单独从城市$2$到城市$3$是无解的。
正确的方法是把“目前已经经过了行程单上的几个城市”$i$(不超过$10$)作为状态的一部分,再加上当前城市编号$j$(注意,最多可能有$400$个城市),以合起来的$(i,j)$为结点构图。构图方法是考虑每张机票的每种用法(飞前面几段),计算出新的状态,用$Dijkstra$来解决。
比如,有一张票$FABCAD$,行程单为$BA$,则以$(0,F)$为起点有$5$条边,分别指向$(0,A)$,$(1,B)$,$(2,A)$和$(2,D)$。
还有几点需要注意:本题最坏情况下可能会用$200$张票,金额超过$100$万美元。另外,虽然题目说答案唯一,但这并不代表图上的最短路是唯一的,因为就算是以相同的顺序使用相同的票,每张票使用的部分也可以不同。
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000, maxn = 4005, maxnt = 105;

struct Edge
{
    int from, to, w, v;
    Edge(int from = 0, int to = 0, int w = 0, int v = 0)
        : from(from), to(to), w(w), v(v)
    {
    }
};

struct HeapNode
{
    int d, u;
    HeapNode(int d = 0, int u = 0) : d(d), u(u) {}
    bool operator<(const HeapNode& rhs) const { return d > rhs.d; }
};

vector<Edge> edges;
vector<int> G[maxn];
bool vis[maxn];  // 是否已永久标号
int d[maxn];     // s到各个点的距离
int p[maxn];     // 最短路中的上一条弧
int n, m;
void init(int n)
{
    ::n = n;
    for (int i = 0; i < n; i++)
        G[i].clear();
    edges.clear();
}

void AddEdge(int from, int to, int w, int v)
{
    edges.push_back((Edge){ from, to, w, v });
    m = edges.size();
    G[from].push_back(m - 1);
}

void Dijkstra(int s)
{
    priority_queue<HeapNode> q;
    for (int i = 0; i < n; i++)
        d[i] = INF;
    d[s] = 0;
    memset(vis, 0, sizeof(vis));
    q.emplace(0, s);
    while (!q.empty())
    {
        HeapNode x = q.top();
        q.pop();
        int u = x.u;
        if (vis[u])
            continue;
        vis[u] = true;
        for (size_t i = 0; i < G[u].size(); i++)
        {
            Edge& e = edges[G[u][i]];
            int v = e.to;
            if (d[v] > d[u] + e.w)
            {
                d[v] = d[u] + e.w;
                p[v] = G[u][i];
                q.emplace(d[v], v);
            }
        }
    }
}
int ccnt;
map<int, int> id;
int read()
{
    int x;
    scanf("%d", &x);
    return x;
}
int ID(int c) { return id.count(c) ? id[c] : id[c] = ccnt++; }
int ID(int v, int cur) { return (v - 1) * ccnt + cur; }

int cost[maxnt];
vector<int> cities[maxnt], iti;

int main()
{
    int NT, kase = 0;
    while (~scanf("%d", &NT) && NT)
    {
        ccnt = 0;
        id.clear();
        for (int i = 0; i < NT; i++)
        {
            cities[i].clear();
            int len;
            scanf("%d%d", &cost[i], &len);
            while (len--)
                cities[i].push_back(ID(read()));
        }
        int NI = read();
        kase++;
        for (int trip = 1; trip <= NI; trip++)
        {
            iti.clear();
            int len = read();
            for (int i = 0; i < len; i++)
                iti.push_back(ID(read()));
            init(ccnt * len);
            for (int i = 0; i < NT; i++)
                for (int j = 1; j < len; j++)
                {
                    int cur = cities[i][0];  // 当前状态为(j, cur)
                    int next = j;  // 下一个需要访问的城市在iti中的下标
                    for (size_t k = 1; k < cities[i].size(); k++)
                    {  // 使用前leg段
                        if (cities[i][k] == iti[next])
                            next++;  // 行程上多经过一个城市
                        AddEdge(ID(j, cur), ID(next, cities[i][k]), cost[i],
                                i + 1);
                        if (next == len)
                            break;  // 行程单已经走完
                    }
                }
            int s = ID(1, iti[0]), t = ID(len, iti[len - 1]);
            Dijkstra(s);
            printf("Case %d, Trip %d: Cost = %d\n", kase, trip, d[t]);
            printf("  Tickets used:");
            vector<int> path;
            while (t != s)
            {
                path.push_back(edges[p[t]].v);
                t = edges[p[t]].from;
            }
            reverse(path.begin(), path.end());
            for (auto x : path)
                printf(" %d", x);
            printf("\n");
        }
    }
    return 0;
}
Last modification:November 6th, 2019 at 05:06 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment