Problem – G – Codeforces

思路

一开始写了一个无脑BFS剪枝求最短路,然后顺带更新最小线路数量,被hack了。

应该直接针对问题处理,通过BFS直接求最小线路数量

这题可以转化成对于一个单点,只有两种选择

  • 走与当前颜色相同的点,答案不变
  • 走与当前颜色不同的点,答案加一

这被描述为 \(01BFS\) ,得利于他只有两个可能性,所以可以用双端队列来维护单调性:

  • 更优的状态放头:即走相同的颜色
  • 更劣的状态放尾:即走不同的颜色

实现

  • 建图

    • 建图有说法的,首先边数点数可能过大,而题目只保证了 \(N\times M\)​ 的空间复杂度合理。

      • 需要牺牲时间换空间,用 std::map 来维护边
    • 维护当前点相连的所有颜色以及所有颜色对应的所有边

      std::vector<std::map<int, std::vector<int>>> adj(n);
      
  • 判重

    • 这里必须定义 \([x, color]\) 两个变量限制的状态来判重才能保证正确性。
  • 01BFS

        std::map<std::pair<int, int>, int> dis;
        std::deque<std::tuple<int, int, int>> q;
        int b, e; std::cin >> b >> e; b--, e--;
        q.emplace_back(0, b, 0);
        //双端队列BFS,意在满足单调最优,求的是最小的地铁线路数
        while(!q.empty()) {
            auto [d, x, color] = q.front();
            q.pop_front();
            if (dis.count({x,  color})) {//如果访问过该点并颜色下的状态就去重
                continue;
            }
            dis[{x,  color}] = d;
            //两种选择,如果颜色相同边权就是0,肯定最优,放到队首。否则放到队尾
            if (color) {//判断不是起点,走相同颜色的边
                q.emplace_front(d, x, 0);
                for (auto& to : adj[x][color]) {
                    q.emplace_front(d + 0, to, color);
                }
            }
            else {//准备走不同颜色的边,先切换当前颜色,地铁线路数加一
                for (auto&[tcolor, _] : adj[x]) {
                    q.emplace_back(d + 1, x, tcolor);
                }
            }
        }
    

代码

void solve() {
    #define tests
    int n, m;
    std::cin >> n >> m;
    std::vector<std::map<int, std::vector<int>>> adj(n);//维护当前点相连的所有颜色以及所有颜色对应的所有边
    for (int i = 0; i < m; i++) {
        int u, v, c;
        std::cin >> u >> v >> c;
        u--, v--;
        adj[u][c].push_back(v);
        adj[v][c].push_back(u);
    }
    std::map<std::pair<int, int>, int> dis;
    std::deque<std::tuple<int, int, int>> q;
    int b, e; std::cin >> b >> e; b--, e--;
    q.emplace_back(0, b, 0);
    //双端队列BFS,意在满足单调最优,求的是最小的地铁线路数
    while(!q.empty()) {
        auto [d, x, color] = q.front();
        q.pop_front();
        if (dis.count({x,  color})) {//如果访问过该点并颜色下的状态就去重
            continue;
        }
        dis[{x,  color}] = d;
        //两种选择,如果颜色相同边权就是0,肯定最优,放到队首。否则放到队尾
        if (color) {//判断不是起点,走相同颜色的边
            q.emplace_front(d, x, 0);
            for (auto& to : adj[x][color]) {
                q.emplace_front(d + 0, to, color);
            }
        }
        else {//准备走不同颜色的边,先切换当前颜色,地铁线路数加一
            for (auto&[tcolor, _] : adj[x]) {
                q.emplace_back(d + 1, x, tcolor);
            }
        }
    }
    std::cout << dis[{e, 0}] << '\n';
}
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。