Dijkstra 算法的堆优化方法

Question

测试使用优先队列优化Dijkstra算法时出现程序错误，对于合法的样例输入测试，输出均为-1。求问题解答
测试用源代码如下：

#include <iostream>  
#include <algorithm>  
#include <queue>  
#include <vector>  
#include <cstring>  
#include <climits>  
using namespace std;
struct node {
    int x, y;
    bool operator<(const node& b) const {
        return y > b.y;
    }
};
int dist[10000];
vector<vector<node>> gh;
int dj(int s, int e) {
    priority_queue<node> pq;
    memset(dist, INT_MAX, sizeof(dist));
    dist[s] = 0;
    pq.push({ s, 0 });
    while (!pq.empty()) {
        node n = pq.top(); pq.pop();
        for (int i = 0; i < gh[n.x].size(); i++) {
            if (dist[gh[n.x][i].x] > dist[n.x] + gh[n.x][i].y) {
                dist[gh[n.x][i].x] = dist[n.x] + gh[n.x][i].y;
                pq.push({ gh[n.x][i].x, dist[gh[n.x][i].x] });
            }
        }
    }
    return dist[e];
}
int main() {
    int t; cin >> t;
    while (t--) {
        int n, e; cin >> n >> e;
        gh.resize(n + 1);
        for (int i = 0; i < e; i++) {
            int u, v, w; cin >> u >> v >> w;
            gh[u].push_back({ v, w });
        }
        int a, b; cin >> a >> b;
        cout << dj(a, b) << endl;
        for (int i = 1; i <= n; i++) {
            gh[i].clear();
        }
    }
    return 0;
}

上图是一个测试样例

Answer 1

望采纳。
你的代码将数组dist的所有元素初始化为INT_MAX的方法是错的(按你的方法会将所有元素初始化为-1)，只需要改一行：
将
memset(dist, INT_MAX, sizeof(dist));
改为
fill(dist,dist+sizeof(dist)/sizeof(dist[0]),INT_MAX);
就行了。
下面是完整代码：

#include <iostream>  
#include <algorithm>  
#include <queue>  
#include <vector>  
#include <cstring>  
#include <climits>  
using namespace std;
struct node {
    int x, y;
    bool operator<(const node& b) const {
        return y > b.y;
    }
};
int dist[10000];
vector<vector<node>> gh;
int dj(int s, int e) {
    priority_queue<node> pq;
    //只需要改这行
    fill(dist,dist+sizeof(dist)/sizeof(dist[0]),INT_MAX);
    //memset(dist, INT_MAX, sizeof(dist));
    dist[s] = 0;
    pq.push({ s, 0 });
    while (!pq.empty()) {
        node n = pq.top(); pq.pop();
        for (int i = 0; i < gh[n.x].size(); i++) {
            if (dist[gh[n.x][i].x] > dist[n.x] + gh[n.x][i].y) {
                dist[gh[n.x][i].x] = dist[n.x] + gh[n.x][i].y;
                pq.push({ gh[n.x][i].x, dist[gh[n.x][i].x] });
            }
        }
    }
    return dist[e];
}
int main() {
    int t; cin >> t;
    while (t--) {
        int n, e; cin >> n >> e;
        gh.resize(n + 1);
        for (int i = 0; i < e; i++) {
            int u, v, w; cin >> u >> v >> w;
            gh[u].push_back({ v, w });
        }
        int a, b; cin >> a >> b;
        cout << dj(a, b) << endl;
        for (int i = 1; i <= n; i++) {
            gh[i].clear();
        }
    }
    return 0;
}