Gemini Flash-Lite 题解

这道题是图论中的“约束路径”问题，本质上依然是广度优先搜索（BFS）。

题目分析

常规的 BFS 状态只用“当前所在节点”表示即可，但这里多了一个约束：不能连续通过两条相同类型的轨道。

为了满足这个约束，我们需要修改 BFS 的状态，使得状态不仅包含“当前节点”，还要包含“上一条轨道的类型”。

定义状态：我们可以将状态表示为 (u, last_c)，其中 u 是当前所在的站点，last_c 是到达 u 时所经过轨道的类型。
状态转移：在节点 u，如果我们尝试走一条类型为 c 的轨道到达 v，必须满足 c != last_c。

解题思路

扩展图结构：对于每一个站点 u，我们需要知道到达它的所有轨道类型。由于轨道类型 c 可能很大（高达），我们不能直接开 dist[N][10^5] 的数组，这会爆内存。
空间优化：使用 vector<pair<int, int>> adj[N] 存储图，adj[u] 中存放 {邻居站点, 轨道类型}。使用 map<pair<int, int>, int> dist 来存储 (u, last_c) 的最短距离。
队列处理：BFS 队列中存入 {u, last_c, current_dist}。

C++ 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

struct State {
    int u, last_c, d;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, S, E;
    cin >> N >> M >> S >> E;

    vector<vector<pair<int, int>>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    // dist[node][last_c] 存储到达该状态的最小步数
    // 使用 map 来处理可能存在的多种轨道类型，避免超大数组
    map<pair<int, int>, int> dist;
    queue<State> q;

    // 初始状态：起点 S，上一条轨道类型设为 0 (表示起点)
    q.push({S, 0, 0});
    dist[{S, 0}] = 0;

    while (!q.empty()) {
        State curr = q.front();
        q.pop();

        if (curr.u == E) {
            cout << curr.d << endl;
            return 0;
        }

        for (auto& edge : adj[curr.u]) {
            int v = edge.first;
            int c = edge.second;

            // 核心约束：不能连续通过两条轨道类型相同的路径
            if (c != curr.last_c) {
                if (dist.find({v, c}) == dist.end()) {
                    dist[{v, c}] = curr.d + 1;
                    q.push({v, c, curr.d + 1});
                }
            }
        }
    }

    cout << -1 << endl;
    return 0;
}

给初学者的特别说明：

状态膨胀：这就是所谓的“状态压缩”或“状态扩展”。原本图上只有个节点，通过引入约束，我们把图“展开”成了个可能的虚拟节点。
为什么不用数组 dist[N][100005]？
虽然且轨道类型也可达，但实际上在一个连通图中，对于任意点 u，合法的 {u, last_c} 组合总数是有限的（取决于总边数）。使用 map 或 unordered_map 可以只存储实际访问过的状态，极大地节省内存空间。
时间复杂度：每个边在每个类型约束下最多被访问一次，复杂度为或，足以应对题目要求。

题目分析

解题思路

C++ 代码实现

给初学者的特别说明：

暂无评论