vector存图堆优化dij

下面是使用堆优化的 Dijkstra 算法来求解最短路径的示例代码，其中使用了 vector 来表示图的邻接表：

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

typedef pair<int, int> pii;

const int INF = numeric_limits<int>::max();

vector<int> dijkstra(const vector<vector<pii>>& graph, int source) {
    int n = graph.size();
    vector<int> dist(n, INF);
    dist[source] = 0;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, source});

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u]) {
            continue;  // 已经找到了更短的路径
        }

        for (const auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;

            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

int main() {
    int n = 5;  // 图的顶点数
    int m = 7;  // 图的边数

    vector<vector<pii>> graph(n);
    
    // 构建图的邻接表
    graph[0].push_back({1, 2});
    graph[0].push_back({2, 4});
    graph[1].push_back({2, 1});
    graph[1].push_back({3, 7});
    graph[2].push_back({3, 3});
    graph[2].push_back({4, 5});
    graph[3].push_back({4, 2});
    graph[4].push_back({3, 1});

    int source = 0;
    vector<int> dist = dijkstra(graph, source);

    cout << "Shortest distances from node " << source << ":" << endl;
    for (int i = 0; i < n; ++i) {
        cout << "Node " << i << ": " << dist[i] << endl;
    }

    return 0;
}

上述代码中，我们使用堆优化的 Dijkstra 算法来找到从源节点到其他节点的最短距离。图的邻接关系使用 vector<vector<pii>> 来表示，其中 pii 表示边的目标节点和权重。你可以根据需要修改图的顶点数、边数和邻接表来适应不同的场景。输出结果将会显示源节点到其他节点的最短距离。