单源最短路径分支限界法代码

以下是单源最短路径分支限界法的 C++ 代码，其中使用了 STL 中的优先队列（priority_queue）：

#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9

using namespace std;

struct Edge {
    int to, weight;
    Edge(int _to, int _weight) : to(_to), weight(_weight) {}
};

struct Node {
    int vertex, cost;
    Node(int _vertex, int _cost) : vertex(_vertex), cost(_cost) {}

    bool operator<(const Node& other) const {
        return cost > other.cost;
    }
};

void shortestPath(vector<vector<Edge>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INF);
    dist[start] = 0;

    priority_queue<Node> pq;
    pq.push(Node(start, 0));

    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();

        int u = cur.vertex;
        int cost = cur.cost;

        if (cost > dist[u]) {
            continue;
        }

        for (int i = 0; i < graph[u].size(); i++) {
            Edge& e = graph[u][i];

            if (dist[u] + e.weight < dist[e.to]) {
                dist[e.to] = dist[u] + e.weight;
                pq.push(Node(e.to, dist[e.to]));
            }
        }
    }

    // 输出最短路径
    for (int i = 0; i < n; i++) {
        cout << "Start: " << start << " End: " << i << " Distance: " << dist[i] << endl;
    }
}

int main() {
    int 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(Edge(v, w));
    }

    shortestPath(graph, 0);

    return 0;
}

其中，`shortestPath` 函数实现了单源最短路径的分支限界算法，使用了优先队列来实现每次取出距起点最近的未访问节点。`dist` 数组记录了起点到每个节点的最短距离，初始化为无穷大，起点距离为 0。在遍历每个节点的邻居节点时，如果通过该邻居节点可以得到更短路径，则更新 `dist` 数组，并将该邻居节点加入优先队列。最后输出起点到每个节点的最短距离。