帮我写一个堆优化的迪杰斯特拉最短路的代码

### 回答1：
以下是使用堆优化的迪杰斯特拉最短路算法的代码实现，代码中使用了一个优先队列来维护待处理的节点。

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

const int INF = 0x3f3f3f3f;
const int MAXN = 100005;

struct Edge {
    int to, w;
    Edge(int t, int weight) : to(t), w(weight) {}
};

vector<Edge> G[MAXN];
int dist[MAXN];
bool vis[MAXN];

void dijkstra(int s) {
    memset(dist, INF, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    dist[s] = 0;
    q.push({dist[s], s});
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto& e : G[u]) {
            int v = e.to, w = e.w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!vis[v]) {
                    q.push({dist[v], v});
                }
            }
        }
    }
}

int main() {
    int n, m, s;
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G[u].emplace_back(v, w);
    }
    dijkstra(s);
    for (int i = 1; i <= n; ++i) {
        if (dist[i] == INF) {
            printf("INF ");
        } else {
            printf("%d ", dist[i]);
        }
    }
    return 0;
}

这段代码实现了堆优化的迪杰斯特拉最短路算法，可以处理有向图和无向图中单源最短路径问题。

### 回答2：
#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

struct Edge {
int to;
int weight;
};

// 定义优先队列的比较规则，按照边的权重大小进行排序
struct cmp {
bool operator()(const Edge& a, const Edge& b) {
return a.weight > b.weight;
}
};

void dijkstra(vector<vector<Edge>>& graph, int start, vector<int>& dist) {
int n = graph.size();

// 初始化距离数组，并将起点的距离设为0
dist.resize(n, numeric_limits<int>::max());
dist[start] = 0;

// 优先队列用于选择权重最小的边
priority_queue<Edge, vector<Edge>, cmp> pq;
pq.push({start, 0});

while (!pq.empty()) {
Edge cur = pq.top();
pq.pop();
int curNode = cur.to;
int curWeight = cur.weight;

// 如果当前边的权重大于已经找到的最短路径，则忽略该边
if (curWeight > dist[curNode]) {
continue;
}

// 遍历当前节点的所有邻接节点
for (const Edge& next : graph[curNode]) {
int nextNode = next.to;
int nextWeight = next.weight;

// 如果通过当前节点到达邻接节点的路径更短，则更新最短路径
if (curWeight + nextWeight < dist[nextNode]) {
dist[nextNode] = curWeight + nextWeight;
pq.push({nextNode, dist[nextNode]});
}
}
}
}

int main() {
int n, m; // n为节点数，m为边数
cin >> n >> m;

// 构建邻接表表示的图
vector<vector<Edge>> graph(n);
for (int i = 0; i < m; i++) {
int u, v, w; // 边的起点、终点和权重
cin >> u >> v >> w;
graph[u].push_back({v, w});
}

int start, end; // 起点和终点
cin >> start >> end;

vector<int> dist;
dijkstra(graph, start, dist);

if (dist[end] == numeric_limits<int>::max()) {
cout << "不存在从起点到终点的路径" << endl;
} else {
cout << "起点到终点的最短路径长度为：" << dist[end] << endl;
}

return 0;
}

### 回答3：
下面是一个使用堆优化的迪杰斯特拉算法的最短路径代码：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典，将起点到每个顶点的距离设为无穷大
    distances = {node: float('inf') for node in graph}
    # 将起点的距离设为0
    distances[start] = 0
    
    # 使用堆来存储当前最小距离的顶点
    heap = [(0, start)]
    
    while heap:
        # 弹出堆中最小距离的顶点
        current_distance, current_node = heapq.heappop(heap)
        
        # 如果当前顶点距离已经大于之前计算的最小距离，则跳过该顶点
        if current_distance > distances[current_node]:
            continue
        
        # 遍历当前顶点的邻居节点
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            # 如果通过当前顶点到达相邻顶点的距离小于之前计算的最小距离，则更新距离并加入堆
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    
    return distances

这个代码使用了字典来表示图，每个顶点作为键，与其相邻顶点及对应的权重作为值。迪杰斯特拉算法的核心是通过不断更新距离字典中的值来获得最短路径。通过使用堆来存储当前最小距离的顶点，可以提高算法的效率。算法首先将起点的距离设为0，然后将起点加入堆中。在每次循环中，弹出堆中的最小距离顶点，并更新其相邻顶点的最小距离。如果通过当前顶点到达相邻顶点的距离小于之前计算的最小距离，则更新距离，并将相邻顶点加入堆中。最后，返回最终的距离字典，其中键为顶点，值为起点到该顶点的最小距离。