带特殊边权的图最短路径计算问题求助

我正在解决一个需考虑普通和特殊两种边权的图最短路径问题，已构建邻接表并使用Dijkstra算法求解，但部分测试用例结果错误。

当前实现思路：

• 图表示：邻接表存储边，每条边包含普通权值和特殊权值
• Dijkstra算法：最小堆优先队列，二维距离数组记录两种权值下的最短距离

怀疑问题出在特殊权值的边松弛处理环节，以下是我的代码：

#include <bits/stdc++.h> 
using namespace std;

typedef pair<int, int> Pair;

struct Edge {
 int v;
 int normal;
 int special;
};

int findShortestDistance(int numberOfVertices, vector<vector<int>> &adj, int src, int dst) {
 vector<vector<Edge>> adjacencyList(numberOfVertices + 1);

 // Building the adjacency list
 for (int i = 0; i < adj.size(); i++) {
     adjacencyList[adj[i][0]].push_back({adj[i][1], adj[i][2], adj[i][3]});
 }

 // Min heap priority queue
 priority_queue<Pair, vector<Pair>, greater<Pair>> minHeap;
 vector<vector<int>> distanceFromSource(numberOfVertices + 1, vector<int>(2, INT_MAX));

 minHeap.push({0, src});
 distanceFromSource[src][0] = 0;

 while (!minHeap.empty()) {
     auto currentPair = minHeap.top();
     minHeap.pop();

     int currentNode = currentPair.second;
     int currentDistance = currentPair.first;

     // Exploring neighbors
     for (auto neighbor : adjacencyList[currentNode]) {
         int neighborNode = neighbor.v;
         int edgeWeight = neighbor.normal;
         int specialWeight = neighbor.special;

         // Relaxing the edge with normal weight
         if (distanceFromSource[neighborNode][0] > currentDistance + edgeWeight) {
             distanceFromSource[neighborNode][0] = currentDistance + edgeWeight;
             minHeap.push({distanceFromSource[neighborNode][0], neighborNode});
         }

         // Relaxing the edge with special weight
         if (distanceFromSource[neighborNode][1] > currentDistance + specialWeight) {
             distanceFromSource[neighborNode][1] = currentDistance + specialWeight;
             // minHeap.push({distanceFromSource[neighborNode][1], neighborNode});
         }
     }
 }

 return min(distanceFromSource[dst][0], distanceFromSource[dst][1]);
}

问题排查与修复 #

核心错误点 #

1. 优先队列缺失状态信息：当前队列仅存储距离和节点，未记录到达该节点时的状态（是否使用过特殊边），导致无法基于特殊路径的距离继续松弛后续节点。
2. 特殊权值更新未入队：注释掉了特殊距离的入队操作，使得通过特殊边得到的更优距离无法被后续处理，大量有效路径被遗漏。
3. 松弛逻辑不完整：未区分当前节点的状态（普通/特殊路径到达），导致无法正确处理两种状态下的边松弛。

修复后的代码 #

#include <bits/stdc++.h> 
using namespace std;

struct Edge {
    int v;
    int normal;
    int special;
};

int findShortestDistance(int numberOfVertices, vector<vector<int>> &adj, int src, int dst) {
    vector<vector<Edge>> adjacencyList(numberOfVertices + 1);

    // 构建邻接表
    for (auto &edge : adj) {
        adjacencyList[edge[0]].push_back({edge[1], edge[2], edge[3]});
    }

    // 优先队列存储：(当前总距离, (当前节点, 状态))，状态0=未使用特殊边，1=已使用特殊边
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> minHeap;
    // distance[node][state]：到达node时，处于state状态的最短距离
    vector<vector<int>> distanceFromSource(numberOfVertices + 1, vector<int>(2, INT_MAX));

    // 初始化起点：未使用特殊边，距离0
    distanceFromSource[src][0] = 0;
    minHeap.push({0, {src, 0}});

    while (!minHeap.empty()) {
        auto [currentDist, nodeState] = minHeap.top();
        minHeap.pop();
        int currentNode = nodeState.first;
        int state = nodeState.second;

        // 如果当前记录的距离比堆中取出的大，说明是过时数据，跳过
        if (currentDist > distanceFromSource[currentNode][state]) {
            continue;
        }

        for (auto &neighbor : adjacencyList[currentNode]) {
            int neighborNode = neighbor.v;
            int normalW = neighbor.normal;
            int specialW = neighbor.special;

            // 情况1：使用普通边，延续当前状态
            if (distanceFromSource[neighborNode][state] > currentDist + normalW) {
                distanceFromSource[neighborNode][state] = currentDist + normalW;
                minHeap.push({distanceFromSource[neighborNode][state], {neighborNode, state}});
            }

            // 情况2：使用特殊边，仅当当前未使用过特殊边时切换状态
            // 若题目允许多次使用特殊边，可移除state == 0的判断
            if (state == 0 && distanceFromSource[neighborNode][1] > currentDist + specialW) {
                distanceFromSource[neighborNode][1] = currentDist + specialW;
                minHeap.push({distanceFromSource[neighborNode][1], {neighborNode, 1}});
            }
        }
    }

    return min(distanceFromSource[dst][0], distanceFromSource[dst][1]);
}

关键修改说明 #

• 队列状态携带：使用三元组存储距离、节点和状态，明确区分到达节点时是否使用过特殊边，确保松弛逻辑的正确性。
• 特殊边入队：修复了特殊权值更新后的入队操作，让特殊路径的距离能参与后续节点的松弛。
• 状态区分松弛：
  • 未使用特殊边时，既可以用普通边延续该状态，也可以用特殊边切换到已使用状态。
  • 已使用特殊边时，只能用普通边延续该状态（若题目允许多次使用特殊边，可移除state == 0的判断）。
• 过时数据跳过：增加距离判断，跳过堆中已失效的旧数据，提升算法效率。

内容的提问来源于stack exchange，提问作者Himanshu