应用分枝限界法的算法设计思想求解单源最短路径问题的C++代码

以下是应用分枝限界法求解单源最短路径问题的C++代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

#define INF 0x3f3f3f3f // 表示无穷大

// 图的邻接表存储结构
struct Edge {
    int to; // 目标节点
    int weight; // 边的权重
    Edge(int _to, int _weight) : to(_to), weight(_weight) {}
};
typedef vector<vector<Edge>> Graph;

// 优先队列中存储的元素
struct Node {
    int pos; // 当前节点
    int dist; // 到当前节点的距离
    Node(int _pos, int _dist) : pos(_pos), dist(_dist) {}

    // 重载小于运算符，用于优先队列排序
    bool operator<(const Node& other) const {
        return dist > other.dist; // 以距离为排序依据
    }
};

// 分枝限界法求解单源最短路径问题
int dijkstra(const Graph& graph, int start, int end) {
    priority_queue<Node> pq;
    pq.emplace(start, 0); // 将起点加入优先队列
    vector<int> dist(graph.size(), INF); // 存储每个节点到起点的最短距离
    dist[start] = 0;

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

        if (cur.pos == end) { // 当前节点是终点，直接返回
            return cur.dist;
        }

        if (cur.dist > dist[cur.pos]) { // 已经有更优的路径，忽略
            continue;
        }

        for (const Edge& edge : graph[cur.pos]) { // 遍历当前节点的邻接节点
            int newDist = cur.dist + edge.weight; // 计算新的距离
            if (newDist < dist[edge.to]) { // 找到更优的路径
                dist[edge.to] = newDist;
                pq.emplace(edge.to, newDist); // 将新节点加入优先队列
            }
        }
    }

    return -1; // 无法到达终点
}

int main() {
    int n, m, start, end;
    cin >> n >> m >> start >> end;

    Graph graph(n + 1); // 使用邻接表存储图

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
    }

    int ans = dijkstra(graph, start, end);
    if (ans == -1) {
        cout << "No path found!" << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

该代码使用了优先队列来选择下一个扩展的节点，使用邻接表存储图，时间复杂度为$O(m\log n)$，其中$n$为节点数，$m$为边数。