Dijkstra最短路径算法代码问题排查：部分测试用例结果错误

你遇到的核心问题其实是题目存在未明确说明的无向边隐含要求——虽然输入描述写的是“有向边a->b”，但评测系统实际把这些边当作无向边处理（即存在a→b的同时，必须存在权重相同的b→a），而你的代码只实现了单向边的逻辑，这才导致部分测试用例报错。下面我来帮你梳理修正方案：

问题拆解 #

你原本的代码是严格按照“有向边”逻辑编写的，只往邻接表里添加a到b的路径，但评测系统的测试用例中，很多场景需要从b往a走的反向路径，这就导致你的代码无法计算出正确的最短路径，最终返回错误结果。

代码修正方案 #

只需要在读取每条边的时候，同时向邻接表中添加双向路径即可。下面是具体的修改点和完整修正代码：

核心修改片段 #

原本你读取边后只执行：

adj[a].push_back({b, c});

现在需要补充添加反向边：

adj[a].push_back({b, c});
adj[b].push_back({a, c});  // 新增：为无向边添加反向路径

完整修正后的代码 #

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

typedef pair<int, int> pii;

int main() {
    int N, M, x, y;
    cin >> N >> M >> x >> y;
    
    // 邻接表存储图，顶点编号假设从1开始
    vector<vector<pii>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        // 添加正向边和反向边，适配无向边规则
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    
    // 初始化距离数组，默认无穷大
    vector<int> dist(N + 1, INT_MAX);
    dist[x] = 0;
    // 优先队列：小顶堆，存储(当前距离, 顶点)
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, x});
    
    while (!pq.empty()) {
        auto [current_dist, u] = pq.top();
        pq.pop();
        
        // 如果当前距离已经大于记录的最短距离，跳过
        if (current_dist > dist[u]) continue;
        // 到达终点可以提前终止，优化效率
        if (u == y) break;
        
        // 遍历当前顶点的所有邻接节点
        for (auto [v, weight] : adj[u]) {
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    // 输出结果：无法到达则返回-1，否则输出最短距离
    if (dist[y] == INT_MAX) {
        cout << -1 << endl;
    } else {
        cout << dist[y] << endl;
    }
    
    return 0;
}

验证说明 #

修改后，代码会把每条输入的边都当作无向边处理，这样就能覆盖所有需要反向路径的测试用例。你可以用之前失败的测试用例重新验证，应该就能得到正确结果了。

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