题目理解

这是一个带状态约束的最短路问题：

• 有 $n$ 个点（娱乐设施），$m$ 条边（道路）
• 每个点有小卖部：1=可乐，2=汉堡
• 每到一个点，大中锋会立即购买并吃掉对应的食物
• 限制：路上任意时刻，汉堡数与可乐数的差值绝对值不能超过 $k$
• 求从 $a$ 到 $b$ 的最短时间

关键点：

• 起点和终点也要算入食物计数
• 状态需要记录当前的食物差值

核心难点

1. 状态依赖：路径的可行性依赖于整个过程中汉堡与可乐的数量关系
2. 状态空间：需要记录当前的位置和食物差值
3. 图规模：$n \leq 10000$，$m \leq 100000$，需要高效算法

解法思路

状态设计

由于 $k \leq 10$，食物差值范围是 $[-k, k]$，我们可以用状态 $(u, diff)$ 表示：

• 当前在节点 $u$
• 当前汉堡数与可乐数的差值 = 汉堡数 - 可乐数

注意：$diff$ 的范围是 $[-k, k]$，超出这个范围就不合法。

状态转移

从状态 $(u, diff)$ 出发：

1. 遍历 $u$ 的所有邻居 $v$
2. 计算到达 $v$ 后的新差值 $new\_diff$：
   • 如果 $v$ 卖汉堡：$new\_diff = diff + 1$
   • 如果 $v$ 卖可乐：$new\_diff = diff - 1$
3. 检查 $new\_diff$ 是否在 $[-k, k]$ 范围内
4. 如果合法，更新最短路

算法选择

使用 Dijkstra 算法，但状态是 $(u, diff)$ 而不是单纯的 $u$。

状态数：$n \times (2k+1) \leq 10000 \times 21 = 210000$，可以接受。

详细算法步骤

1. 初始化：

   • $dist[u][diff]$ 表示到达节点 $u$ 且差值为 $diff$ 的最短时间
   • 初始化为无穷大
   • 起点状态：根据起点卖的食物初始化 $diff$
     • 起点卖汉堡：$diff = 1$
     • 起点卖可乐：$diff = -1$
   • 检查起点 $diff$ 是否合法（在 $[-k,k]$ 内）

2. Dijkstra：

   • 优先队列按时间从小到大处理状态 $(u, diff, time)$
   • 对于每个状态，遍历所有邻居 $v$
   • 计算新差值，检查合法性
   • 如果新状态时间更短，更新并入队

3. 答案：

   • 取终点 $b$ 的所有合法 $diff$ 状态中的最小时间
   • 如果没有合法状态，输出 $-1$

复杂度分析

• 状态数：$O(n \cdot k)$
• 边数：$O(m \cdot k)$（每个状态可能扩展多条边）
• 总复杂度：$O(k \cdot (n \log n + m \log n))$，可以接受

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;

const int MAXN = 10005;
const int MAXK = 12;
const int INF = INT_MAX;

struct Node {
    int u, diff, time;
    Node(int _u, int _diff, int _time) : u(_u), diff(_diff), time(_time) {}
    bool operator<(const Node& other) const {
        return time > other.time;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n, m, k;
        cin >> n >> m >> k;
        
        vector<int> type(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> type[i];
        }
        
        vector<vector<pair<int, int>>> graph(n + 1);
        for (int i = 0; i < m; i++) {
            int p, q, t;
            cin >> p >> q >> t;
            graph[p].emplace_back(q, t);
            graph[q].emplace_back(p, t);
        }
        
        int a, b;
        cin >> a >> b;
        
        // dist[u][diff]：到达u点，差值=diff的最短时间
        vector<vector<int>> dist(n + 1, vector<int>(2 * k + 3, INF));
        
        // 起点初始化
        int start_diff;
        if (type[a] == 1) { // 可乐
            start_diff = -1;
        } else { // 汉堡
            start_diff = 1;
        }
        
        // 检查起点是否合法
        if (abs(start_diff) > k) {
            cout << -1 << '\n';
            continue;
        }
        
        // 差值映射到数组索引：diff + k
        dist[a][start_diff + k] = 0;
        priority_queue<Node> pq;
        pq.emplace(a, start_diff + k, 0);
        
        int ans = INF;
        
        while (!pq.empty()) {
            Node cur = pq.top();
            pq.pop();
            
            int u = cur.u;
            int diff_idx = cur.diff;
            int cur_time = cur.time;
            int actual_diff = diff_idx - k;
            
            if (cur_time > dist[u][diff_idx]) {
                continue;
            }
            
            // 到达终点，更新答案
            if (u == b) {
                ans = min(ans, cur_time);
            }
            
            for (auto& edge : graph[u]) {
                int v = edge.first;
                int cost = edge.second;
                
                // 计算新差值
                int new_diff = actual_diff;
                if (type[v] == 1) { // 可乐
                    new_diff--;
                } else { // 汉堡
                    new_diff++;
                }
                
                // 检查差值是否合法
                if (abs(new_diff) > k) {
                    continue;
                }
                
                int new_diff_idx = new_diff + k;
                int new_time = cur_time + cost;
                
                if (new_time < dist[v][new_diff_idx]) {
                    dist[v][new_diff_idx] = new_time;
                    pq.emplace(v, new_diff_idx, new_time);
                }
            }
        }
        
        if (ans == INF) {
            cout << -1 << '\n';
        } else {
            cout << ans << '\n';
        }
    }
    
    return 0;
}

样例验证

样例1

输入：
1
2 1 1
1 1
1 2 1
1 2

过程：
- 起点1：卖可乐 → diff = -1
- 到点2：卖可乐 → diff = -2
- | -2 | > k=1，不合法
输出：-1

样例2

输入：
1
2 1 2  
1 1
1 2 1
1 2

过程：
- 起点1：卖可乐 → diff = -1
- 到点2：卖可乐 → diff = -2  
- | -2 | ≤ k=2，合法
输出：1

优化点

1. 提前终止：当从优先队列中取出终点状态时，可以直接返回答案
2. 状态压缩：可以用位运算将 $(u, diff)$ 压缩成一个整数
3. 内存优化：使用二维数组而不是 vector of vectors

总结

本题的关键在于将路径约束转化为状态空间的扩展：

• 用 $(节点, 差值)$ 作为状态
• 使用 Dijkstra 在状态图上求最短路
• 利用 $k$ 较小的特点控制状态数

这种方法可以推广到其他带有计数约束的最短路问题。