采用BFS和DFS求解带权图最短路径，使用C++

在C++中，使用BFS（广度优先搜索）和DFS（深度优先搜索）来求解带权图的最短路径，一般我们会选择BFS，因为它是保证找到最短路径的有效方法。这里我会展示一个简单的BFS实现，假设我们已经有了一个邻接矩阵`adjMatrix`来表示图，以及一个函数`getWeight(i, j)`获取从城市i到j的边的权重。

首先，我们假设所有的权重都是非负的，因为负权重的情况需要使用其他算法，比如迪杰斯特拉(Dijkstra)或Floyd-Warshall。

以下是使用BFS的C++代码示例：

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

// 获取权重
int getWeight(int i, int j, vector<vector<int>>& adjMatrix) {
    // 实际的实现依赖于您的图模型，此处仅作为占位符
    return adjMatrix[i][j];
}

// 广度优先搜索
pair<int, vector<int>> bfs(vector<vector<int>>& adjMatrix, int start, int end) {
    vector<bool> visited(adjMatrix.size(), false);
    vector<int> distances(adjMatrix.size(), INT_MAX); // 初始化所有距离为最大值
    distances[start] = 0; // 起点的距离为0

    queue<int> q;
    q.push(start);

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (int neighbor : adjMatrix[curr]) { // 遍历邻居
            int weight = getWeight(curr, neighbor, adjMatrix);
            if (visited[neighbor] || weight > distances[curr]) continue;

            distances[neighbor] = distances[curr] + weight;
            q.push(neighbor);
        }

        visited[curr] = true;
    }

    if (distances[end] == INT_MAX) return {INT_MAX, {}}; // 如果未找到路径，则返回无穷大

    vector<int> path;
    for (int node = end; node != start; node = parent[node]) { // 逆序构建路径
        path.push_back(node);
    }
    path.push_back(start); // 包含起始节点
    reverse(path.begin(), path.end());

    return {distances[end], path};
}

int main() {
    // 初始化邻接矩阵和其他变量...
    auto result = bfs(adjMatrix, A, E); // A是起始城市，E是目标城市
    cout << "Shortest path distance: " << result.first << endl;
    cout << "Path: ";
    for (auto& city : result.second) {
        cout << city << " -> ";
    }
    cout << "A" << endl;
    return 0;
}