PAT-天梯赛习题集-L3-014-周游世界

ACM模版

描述

题解

说实在的，这道题我没有完全解决，所以写这个博客不是为了帮助别人解决这个问题，而是希望有朋友帮我找到我的 bug，我找了大半天也没有找到问题所在，30分只得了19分，尴尬症犯了。

为了方便大神们看我的代码，我先写一下自己的思路，这里我用的 Dijkstra 的队列+邻接表（堆）优化解法，多标签搜索，除了基础的距离 dist[]、vis[]，我又开了三个标签，pre[]：存储父节点，记录路径，pre_[]：父节点所在路线（转接点算到上一条路线），cnt[]：累计经过路线数目。

另外需要说明的是，题目规定，每一个运营区间只会承包给一家公司，所以我又在邻接表中添加了一个公司（线路）标签，记录每一个区间所承包的公司（线路）。其他过程和普通的 dijkstra 算法没有什么区别，但是就是莫名其妙的挂了11组数据，请求大神们悉心查阅，如果发现了我的 bug 并知会与我，我将十分感谢，万分膜拜~~~

问题代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>

using namespace std;

/* * 使用优先队列优化Dijkstra算法 * 复杂度O(ElongE) * 注意对vector<Edge> E[MAXN]进行初始化后加边 */

const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;

struct qNode
{
    int v;
    int c;
    qNode(int _v = 0, int _c = 0) : v(_v), c(_c) {}
    bool operator < (const qNode &r) const
    {
        return c > r.c;
    }
};

struct Edge
{
    int v;
    int cost;
    Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};

vector<pair<Edge, int> > E[MAXN];
bool vis[MAXN];
int dist[MAXN];     // 最短路距离
int pre[MAXN];      // 父节点，记录路径
int pre_[MAXN];     // 父节点所在路线（转接点算到上一条路线）
int cnt[MAXN];      // 累计经过路线数目

void Dijkstra(int n, int start)     // 点的编号从1开始
{
    memset(vis, false, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist));
    memset(pre, -1, sizeof(pre));
    memset(pre_, -1, sizeof(pre_));
    memset(cnt, -1, sizeof(cnt));
    priority_queue<qNode> que;

    while (!que.empty())
    {
        que.pop();
    }
    dist[start] = 0;
    que.push(qNode(start, 0));
    qNode tmp;

    while (!que.empty())
    {
        tmp = que.top();
        que.pop();
        int u = tmp.v;
        if (vis[u])
        {
            continue;
        }
        vis[u] = true;
        for (int i = 0; i < E[u].size(); i++)
        {
            int v = E[u][i].first.v;
            int cost = E[u][i].first.cost;
            if (!vis[v] && dist[v] > dist[u] + cost)
            {
                dist[v] = dist[u] + cost;
                pre[v] = u;
                if (pre_[u] == -1 || E[u][i].second != pre_[u])
                {
                    if (pre_[u] == -1)
                    {
                        pre_[u] = E[u][i].second;
                        cnt[u] = 1;
                    }
                    pre_[v] = E[u][i].second;
                    cnt[v] = pre_[v] == pre_[u] ? cnt[u] : cnt[u] + 1;
                }
                else
                {
                    pre_[v] = pre_[u];
                    cnt[v] = cnt[u];
                }
                que.push(qNode(v, dist[v]));
            }
            else if (!vis[v] && dist[v] == dist[u] + cost)
            {
                if (E[u][i].second == pre_[u])
                {
                    if (cnt[pre[v]] > cnt[u])
                    {
                        pre[v] = u;
                        pre_[v] = pre_[u];
                        cnt[v] = cnt[u];
                        que.push(qNode(v, dist[v]));
                    }
                }
                else
                {
                    if (cnt[pre[v]] > cnt[u] + 1)
                    {
                        pre[v] = u;
                        pre_[v] = E[u][i].second;
                        cnt[v] = cnt[u] + 1;
                        que.push(qNode(v, dist[v]));
                    }
                }
            }
        }
    }
}

void addEdge(int u, int v, int w, int c)
{
    E[u].push_back(make_pair(Edge(v, w), c));
}

struct way
{
    int id;
    int cmp;
} w[MAXN];

void getWay(int ed, int mt)
{
    int m = mt;
    w[m].id = ed;
    w[m--].cmp = pre_[ed];
    while (pre[ed] != -1)
    {
        ed = pre[ed];
        w[m].id = ed;
        w[m--].cmp = pre_[ed];
    }
    w[1].id = ed;
    w[1].cmp = pre_[ed];

    int sc = w[1].cmp;
    int si = w[1].id;
    for (int i = 2; i <= mt; i++)
    {
        if (w[i].cmp != sc)
        {
            printf("Go by the line of company #%d from %04d to %04d.\n", sc, si, w[i - 1].id);
            sc = w[i].cmp;
            si = w[i - 1].id;
        }
    }
    printf("Go by the line of company #%d from %04d to %04d.\n", sc, si, w[mt].id);
}

int main()
{
// freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    int N;
    cin >> N;

    int M, u, v;
    for (int i = 1; i <= N; i++)
    {
        scanf("%d%d", &M, &u);
        for (int j = 1; j < M; j++)
        {
            scanf("%d", &v);
            addEdge(u, v, 1, i);
            addEdge(v, u, 1, i);
            u = v;
        }
    }

    int K;
    cin >> K;
    for (int i = 0; i < K; i++)
    {
        scanf("%d%d", &u, &v);
        Dijkstra(N, u);
        if (dist[v] == INF)
        {
            cout << "Sorry, no line is available.\n";
        }
        else
        {
            cout << dist[v] << '\n';
            getWay(v, dist[v] + 1);
        }
    }

    return 0;
}

2017.3.31 1:36 更新

根据评论区大牛 欣君 提供的一组样例，我进行了一些修正，将getWay()函数做了微调整，从原来的 19 分变成了 25 分，除了第三组外其他两组原来没有通过的样例通过了，但是，我依然没有成功 AC，哎，伤脑筋啊，还有啥 bug 啊~~~哭晕在键盘上:-)

修改 One

void getWay(int ed, int mt);

void getWay(int ed, int mt)
{
    int m = mt;
    w[m].id = ed;
    w[m--].cmp = pre_[ed];
    while (pre[ed] != -1)
    {
        ed = pre[ed];
        w[m].id = ed;
        w[m--].cmp = pre_[ed];
    }
    w[1].id = ed;
    w[1].cmp = pre_[ed];
    if (w[1].cmp != w[2].cmp)   //  此判断为最新修改
    {
        w[1].cmp = w[2].cmp;
    }

    int sc = w[1].cmp;
    int si = w[1].id;
    for (int i = 2; i <= mt; i++)
    {
        if (w[i].cmp != sc)
        {
            printf("Go by the line of company #%d from %04d to %04d.\n", sc, si, w[i - 1].id);
            sc = w[i].cmp;
            si = w[i - 1].id;
        }
    }
    printf("Go by the line of company #%d from %04d to %04d.\n", sc, si, w[mt].id);
}

这样改，可以成功避免起点自成一路的情况，毕竟自成一路也就意味着没有经过该路线的任一区间，这样不合法。

另外，发现题目有漏洞，让输出经停站数量（始发地和目的地不包括在内），可是最后结果却比真实结果大一，也就是说，始发地和目的地有一个包含在内了，例如样例中：3011 - 3013 的具体路线为 3011 - 3812 - 3013，也就是说，除去始发地和目的地外，经停站应该为1才对，而样例结果却为2，所以这是题目的一个漏洞。

2017.4.1 0:55 更新

十分感谢评论区 欣君 大神，又给我提供了一组错误样例，助我成功找到 bug。

对于大神所言，我没有考虑在站数最少的情况下线路数要最少的规定，实际上不然，我考虑了，然而 bug 导致我的线路修正出了问题，由于我想到了这个问题，所以找 bug 时我以为我考虑过了，所以就没有仔细斟酌这个过程，然而大神给我提供的样例告诉我，我的处理没有成功，究其原因，是搞错了一个 if 判断并且少了一个起点的特殊处理，修改位置均在 Dijkstra() 函数中。

修改 Two

void Dijkstra(int n, int start);

void Dijkstra(int n, int start)     // 点的编号从1开始
{
    memset(vis, false, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist));
    memset(pre, -1, sizeof(pre));
    memset(pre_, -1, sizeof(pre_));
    memset(cnt, -1, sizeof(cnt));
    priority_queue<qNode> que;

    while (!que.empty())
    {
        que.pop();
    }
    dist[start] = 0;
    que.push(qNode(start, 0));
    qNode tmp;

    while (!que.empty())
    {
        tmp = que.top();
        que.pop();
        int u = tmp.v;
        if (vis[u])
        {
            continue;
        }
        vis[u] = true;
        for (int i = 0; i < E[u].size(); i++)
        {
            int v = E[u][i].first.v;
            int cost = E[u][i].first.cost;
            if (!vis[v] && dist[v] > dist[u] + cost)
            {
                dist[v] = dist[u] + cost;
                pre[v] = u;
                if (pre_[u] == -1 || E[u][i].second != pre_[u] || u == start)   // 4.1
                {
                    if (pre_[u] == -1 || u == start)    // 4.1
                    {
                        pre_[u] = E[u][i].second;
                        cnt[u] = 1;
                    }
                    pre_[v] = E[u][i].second;
                    cnt[v] = pre_[v] == pre_[u] ? cnt[u] : cnt[u] + 1;
                }
                else
                {
                    pre_[v] = pre_[u];
                    cnt[v] = cnt[u];
                }
                que.push(qNode(v, dist[v]));
            }
            else if (!vis[v] && dist[v] == dist[u] + cost)
            {
                if (E[u][i].second == pre_[u])
                {
                    if (cnt[v] > cnt[u])        // 4.1
                    {
                        pre[v] = u;
                        pre_[v] = pre_[u];
                        cnt[v] = cnt[u];
                        que.push(qNode(v, dist[v]));
                    }
                }
                else
                {
                    if (cnt[v] > cnt[u] + 1)    // 4.1
                    {
                        pre[v] = u;
                        pre_[v] = E[u][i].second;
                        cnt[v] = cnt[u] + 1;
                        que.push(qNode(v, dist[v]));
                    }
                }
            }
        }
    }
}

终于拿到30分了，十分开心，为了方便大家查看代码，完整的正确代码再贴一遍喽~~~

AC 代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

/* * 使用优先队列优化Dijkstra算法 * 复杂度O(ElongE) * 注意对vector<Edge> E[MAXN]进行初始化后加边 */

const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;

struct qNode
{
    int v;
    int c;
    qNode(int _v = 0, int _c = 0) : v(_v), c(_c) {}
    bool operator < (const qNode &r) const
    {
        return c > r.c;
    }
};

struct Edge
{
    int v;
    int cost;
    Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};

vector<pair<Edge, int> > E[MAXN];
bool vis[MAXN];
int dist[MAXN];     // 最短路距离
int pre[MAXN];      // 父节点，记录路径
int pre_[MAXN];     // 父节点所在路线（转接点算到上一条路线）
int cnt[MAXN];      // 累计经过路线数目

void Dijkstra(int n, int start)     // 点的编号从1开始
{
    memset(vis, false, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist));
    memset(pre, -1, sizeof(pre));
    memset(pre_, -1, sizeof(pre_));
    memset(cnt, -1, sizeof(cnt));
    priority_queue<qNode> que;

    while (!que.empty())
    {
        que.pop();
    }
    dist[start] = 0;
    que.push(qNode(start, 0));
    qNode tmp;

    while (!que.empty())
    {
        tmp = que.top();
        que.pop();
        int u = tmp.v;
        if (vis[u])
        {
            continue;
        }
        vis[u] = true;
        for (int i = 0; i < E[u].size(); i++)
        {
            int v = E[u][i].first.v;
            int cost = E[u][i].first.cost;
            if (!vis[v] && dist[v] > dist[u] + cost)
            {
                dist[v] = dist[u] + cost;
                pre[v] = u;
                if (pre_[u] == -1 || E[u][i].second != pre_[u] || u == start)   // 4.1
                {
                    if (pre_[u] == -1 || u == start)    // 4.1
                    {
                        pre_[u] = E[u][i].second;
                        cnt[u] = 1;
                    }
                    pre_[v] = E[u][i].second;
                    cnt[v] = pre_[v] == pre_[u] ? cnt[u] : cnt[u] + 1;
                }
                else
                {
                    pre_[v] = pre_[u];
                    cnt[v] = cnt[u];
                }
                que.push(qNode(v, dist[v]));
            }
            else if (!vis[v] && dist[v] == dist[u] + cost)
            {
                if (E[u][i].second == pre_[u])
                {
                    if (cnt[v] > cnt[u])        // 4.1
                    {
                        pre[v] = u;
                        pre_[v] = pre_[u];
                        cnt[v] = cnt[u];
                        que.push(qNode(v, dist[v]));
                    }
                }
                else
                {
                    if (cnt[v] > cnt[u] + 1)    // 4.1
                    {
                        pre[v] = u;
                        pre_[v] = E[u][i].second;
                        cnt[v] = cnt[u] + 1;
                        que.push(qNode(v, dist[v]));
                    }
                }
            }
        }
    }
}

void addEdge(int u, int v, int w, int c)
{
    E[u].push_back(make_pair(Edge(v, w), c));
}

struct way
{
    int id;
    int cmp;
} w[MAXN];

void getWay(int ed, int mt)
{
    int m = mt;
    w[m].id = ed;
    w[m--].cmp = pre_[ed];
    while (pre[ed] != -1)
    {
        ed = pre[ed];
        w[m].id = ed;
        w[m--].cmp = pre_[ed];
    }
    w[1].id = ed;
    w[1].cmp = pre_[ed];
    if (w[1].cmp != w[2].cmp)   // 3.31
    {
        w[1].cmp = w[2].cmp;
    }

    int sc = w[1].cmp;
    int si = w[1].id;
    for (int i = 2; i <= mt; i++)
    {
        if (w[i].cmp != sc)
        {
            printf("Go by the line of company #%d from %04d to %04d.\n", sc, si, w[i - 1].id);
            sc = w[i].cmp;
            si = w[i - 1].id;
        }
    }
    printf("Go by the line of company #%d from %04d to %04d.\n", sc, si, w[mt].id);
}

int main()
{
// freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    int N;
    cin >> N;

    int M, u, v;
    for (int i = 1; i <= N; i++)
    {
        scanf("%d%d", &M, &u);
        for (int j = 1; j < M; j++)
        {
            scanf("%d", &v);
            addEdge(u, v, 1, i);
            addEdge(v, u, 1, i);
            u = v;
        }
    }

    int K;
    cin >> K;
    for (int i = 0; i < K; i++)
    {
        scanf("%d%d", &u, &v);
        Dijkstra(N, u);
        if (dist[v] == INF)
        {
            cout << "Sorry, no line is available.\n";
        }
        else
        {
            cout << dist[v] << '\n';
            getWay(v, dist[v] + 1);
        }
    }

    return 0;
}