「UVa 1599」Ideal Path - 最短路 + BFS

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

UVa 链接

给定一个 \(n\) 个点 \(m\) 条边的无向图，每条边上都涂有 \(1\) 种颜色。求点 \(1\) 到点 \(n\) 的一条路径，使得经过的边数最少，在此前提下，经过边的颜色序列最小。可能有自环与重边。输入保证至少存在一条连接 \(1\) 和 \(n\) 的道路。

解题思路

本题为求图论最短路，由于不需要考虑边权，可使用 BFS。

这道题在路径最短的情况下使得颜色所组成的字典序最小，可以分开解决。

首先解决最短路问题，求出所有的从 \(1\) 到 \(n\) 的最短路路径。这一步可通过记录从 \(n\) 到 \(1\) 可到达所有点的步数即可。利用该方法可从 \(1\) 遍历可达路径，只要满足在记录中将达到的点的步数为之前的点的步数减一即为从 \(1\) 到 \(n\) 的最短路或最短路的一部分，这一步可通过 BFS 解决，代码中对应的是 bfsK 函数。

接下来就要解决字典序最小。我们需要再一次使用 BFS 以求出在所有最短路中字典序最小的一条。由于最终长度相同，我们始终仅需选择字典序最小的节点。若两节点字典序相同，则都存入考虑范围。由于该次 BFS 无需进行队列弹出操作，且存入的节点同一层可能有多个，存储全部队列空间可能会爆，所以我们需要将队列改写滚动样式，仅存储最上层和次上层即可。代码中对应的是 bfsCol 函数。

注意在 bfsCol 函数中合理处理最短路步数的标记。同时注意应在全部字典序的节点都压入队列时再进行滚动操作。

代码演示

这次 AC 代码有点丑，请见谅 ≧ ﹏ ≦

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

const int MAXN = 100000, INF = 200000;

int n, m;
std::vector< std::pair<int, int> > e[MAXN + 1];
int vis[MAXN + 1], ans;
int col[INF + 1];

void bfsK() {
    static std::queue< std::pair<int, int> > qK;
    memset(vis, -1, sizeof(vis));
    qK.push( std::make_pair(n, 0) );
    vis[n] = 0, ans = INF;

    while (!qK.empty()) {
        auto u = qK.front();
        qK.pop();
        if (u.first == 1 && u.second < ans) ans = u.second;
        for (auto ed : e[u.first]) {
            if (vis[ed.first] == -1) {
                vis[ed.first] = u.second + 1;
                qK.push(std::make_pair(ed.first, u.second + 1));
            }
        }
    }
}

void bfsCol() {
    static std::vector<int> qCol;
    static bool mk[MAXN + 1];  // 此为已访问节点的标记
    memset(col, 0x3f, sizeof(col));
    memset(mk, false, sizeof(mk));
    qCol.clear();
    qCol.push_back(1);

    int cnt = ans - 1;
    bool flag = true;
    while (cnt >= 0) {
        static std::vector<int> uSet;
        if (flag) {  // 注意滚动的时机
            uSet.clear();
            for (int each : qCol) uSet.push_back(each);
            qCol.clear();
        }
        flag = true;
        for (int u : uSet) {
            for (auto ed : e[u]) {
                if (vis[ed.first] == cnt) {
                    if (!mk[ed.first]) {
                        if (col[cnt] >= ed.second) {
                            if (col[cnt] > ed.second) qCol.clear();
                            col[cnt] = ed.second;
                            mk[ed.first] = true;
                            flag = false;
                            qCol.push_back(ed.first);
                        }
                    } else if (col[cnt] > ed.second) col[cnt] = ed.second;
                }
            }
        }
        if (flag) {  // 若无符合条件的节点，说明已遍历完。最短路步数加一。
            cnt--;
            for (int u : uSet) {
                for (auto ed : e[u]) {
                    if (vis[ed.first] == cnt) {
                        if (!mk[ed.first]) {
                            if (col[cnt] >= ed.second) {
                                if (col[cnt] > ed.second) qCol.clear();
                                col[cnt] = ed.second;
                                mk[ed.first] = true;
                                flag = false;
                                qCol.push_back(ed.first);
                            }
                        } else if (col[cnt] > ed.second) col[cnt] = ed.second;
                    }
                }
            }
        }
    }
}

int main() {
    while (std::cin >> n >> m) {
        for (int i = 1; i <= n; i++) e[i].clear();

        for (int i = 0, x, y, z; i < m; i++) {
            scanf("%d%d%d", &x, &y, &z);
            if (x == y) continue;
            e[x].push_back( std::make_pair(y, z) );
            e[y].push_back( std::make_pair(x, z) );
        }

        for (int i = 1; i <= n; i++) std::sort(e[i].begin(), e[i].end());

        bfsK();
        bfsCol();

        std::cout << ans << std::endl;
        // UVA毒瘤！卡我输出格式！
        for (int i = ans - 1; i >= 0; i--) printf("%d%c", col[i], i == 0 ? '\n' : ' ');
    }

    return 0;
}