djkstra模板c++堆优化

你可以使用Dijkstra算法的堆优化版本来解决最短路径问题。下面是一个C++的模板示例：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

typedef pair<int, int> pii; // 用于表示图中的边

vector<int> dijkstra(vector<vector<pii>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX); // 初始化距离向量
    vector<bool> visited(n, false); // 初始化访问标记向量
    
    // 使用优先队列实现堆优化
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    
    dist[start] = 0; // 初始节点的距离为0
    pq.push({0, start}); // 将初始节点加入优先队列

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        if (visited[u]) {
            continue;
        }
        
        visited[u] = true;
        
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

int main() {
    int n, m;
    cout << "请输入图中的节点数和边数: ";
    cin >> n >> m;
    
    vector<vector<pii>> graph(n);
    
    cout << "请输入每条边的起点、终点和权重: " << endl;
    
    for (int i = 0; i < m; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        
        graph[u].push_back({v, weight});
        graph[v].push_back({u, weight});
    }
    
    int start;
    cout << "请输入起始节点: ";
    cin >> start;
    
    vector<int> shortestPath = dijkstra(graph, start);
    
    cout << "从起点到各个节点的最短距离为: " << endl;
    
    for (int i = 0; i < n; i++) {
        cout << "到节点 " << i << " 的最短距离为: " << shortestPath[i] << endl;
    }

    return 0;
}

你可以根据需要修改输入和输出的格式，以及将代码集成到你的项目中。这个模板使用了优先队列来实现堆优化，以提高Dijkstra算法的效率。