.Alpha. 2024-08-13 22:54 采纳率: 66.7%

# Dijkstra 算法的堆优化方法

``````#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;
}
``````

• 写回答

#### 12条回答默认 最新

• micthis 2024-08-14 09:52
关注

望采纳。
你的代码将数组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;
}
``````

本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论 编辑记录

• 系统已结题 8月22日
• 已采纳回答 8月14日
• 创建了问题 8月13日

#### 悬赏问题

• ¥15 软件供应链安全是跟可靠性有关还是跟安全性有关？
• ¥15 电脑蓝屏logfilessrtsrttrail问题
• ¥20 关于wordpress建站遇到的问题！(语言-php)（相关搜索：云服务器）
• ¥15 【求职】怎么找到一个周围人素质都很高不会欺负他人，并且未来月薪能够达到一万以上（技术岗）的工作？希望可以收到写有具体，可靠，已经实践过了的路径的回答？
• ¥15 Java+vue部署版本反编译
• ¥100 对反编译和ai熟悉的开发者。
• ¥15 带序列特征的多输出预测模型
• ¥15 Python 如何安装 distutils模块
• ¥15 关于#网络#的问题：网络是从楼上引一根网线下来，接了2台傻瓜交换机，也更换了ip还是不行
• ¥15 资源泄露软件闪退怎么解决？