c++_单源最短路求解

Question

c++单源最短路

ZJYYC在线测评系统 https://acm.creative3605.com/contest/132/problem/B

Answer 1

引自免费微信小程序：皆我百晓生

要解决这个问题，我们可以使用Dijkstra算法来找到从给定起点到所有其他顶点的最短路径。首先，我们需要了解题目描述，但是提供的链接（ZJYYC在线测评系统）可能需要登录或者是在特定时间范围内才能访问。

这里是一个基本的Dijkstra算法的C++实现，用于解决单源最短路径问题。这个算法假设边的权重非负。如果你有带负权边的情况，可以考虑使用Bellman-Ford算法或者Johnson's Algorithm。

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

using namespace std;

const int INF = INT_MAX;

// 定义一个结构体表示图中的节点
struct Node {
    int id;
    vector<pair<int, int>> edges; // 存储每个节点的邻接节点及其边的权重
};

// 优先队列用于存储待处理的节点，优先级是根据距离来的
struct CompareNodes {
    bool operator()(Node const& a, Node const& b) {
        return a.distance > b.distance;
    }
};

void dijkstra(vector<Node>& graph, int start) {
    int num_nodes = graph.size();
    vector<int> distance(num_nodes, INF);
    vector<bool> visited(num_nodes, false);

    // 初始化起始节点的距离为0
    distance[start] = 0;

    priority_queue<Node, vector<Node>, CompareNodes> pq;
    pq.push({start, distance});

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

        if (visited[current.id]) continue;

        visited[current.id] = true;

        for (auto edge : current.edges) {
            int neighbor_id = edge.first;
            int weight = edge.second;

            // 计算通过当前节点到达邻居节点的新距离
            int new_distance = current.distance + weight;

            // 如果新距离小于已知距离，则更新距离并把邻居节点放入优先队列
            if (new_distance < distance[neighbor_id]) {
                distance[neighbor_id] = new_distance;
                pq.push({neighbor_id, distance});
            }
        }
    }

    // 输出结果
    for (int i = 0; i < num_nodes; ++i) {
        cout << "Distance from node " << start << " to node " << i << ": "
             << (distance[i] == INF ? "INF" : to_string(distance[i])) << endl;
    }
}

int main() {
    // 根据实际输入数据填充graph和start节点
    vector<Node> graph;
    int start = 0; // 假设起始节点为0

    dijkstra(graph, start);

    return 0;
}

为了完成整个程序，你需要读取输入数据，并将它们转换成上述Node结构体数组。然后调用dijkstra函数，传入图和起始节点的索引。注意，这个例子中的代码没有包含输入部分，因为这取决于具体的测试数据格式。

请确保理解这段代码的工作原理，包括Dijkstra算法的基本思想、优先队列的使用以及如何遍历图。如果有任何不清楚的地方，请随时提问。