题解 | #【模板】单源最短路1# BFS

【模板】单源最短路1

https://www.nowcoder.com/practice/f24504c9ff544f7c808f76693cc34af8

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

using namespace std;

int shortest_path(int n, int m, vector<pair<int, int>>& edges) {
    // 构建邻接表
    vector<vector<int>> graph(n+5000);
    for(auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        // 无向图，双向都加入邻接列表
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    // 初始化距离数组
    vector<int> dist(n+5000, numeric_limits<int>::max());
    dist[1] = 0;

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

    //广度优先搜索
    while(!q.empty()) {
        int u = q.front();
        q.pop();

        for(int v : graph[u]) {
           if(dist[v] == numeric_limits<int>::max()) {
 dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    if(dist[n] == numeric_limits<int>::max()) {
        return -1;
    } else {
        return dist[n];
    }
}

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

    vector<pair<int, int>> edges;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges.emplace_back(make_pair(u,v));
    }

    // 调用函数求解最短距离
    int result = shortest_path(n, m, edges);

    // 输出结果
    cout << result << endl;

    return 0;
}

这是一个求解图中从节点1到节点n的最短路径长度的问题，使用的是广度优先搜索算法。

首先，构建一个邻接表 graph，其中每个节点都是一个向量，存储了与其相邻节点的编号。这样，可以通过遍历邻接表来获取每个节点的相邻节点。

接下来，初始化一个距离数组 dist，将每个节点的距离初始设置为最大值。接着，将节点1的距离设置为0，并将其加入到队列 q 中。

在广度优先搜索过程中，每次从队列 q 中取出一个节点 u，然后遍历节点 u 的相邻节点。如果相邻节点 v 的距离为最大值（表示未被访问过），则更新节点 v 的距离为节点 u 的距离加一，并将节点 v 加入到队列 q 中。

最终，如果节点n的距离仍然为最大值，则表示无法从节点1到达节点n，返回-1；否则，返回节点n的距离，即最短路径的长度。

请注意，为了确保足够的节点和边数，将邻接表和距离数组的大小都设置为 n + 5000。一般来说，为了避免因为图的规模太大而发生数组越界的问题，应该根据实际问题规模来设置合适的大小。

补充

numeric_limits<int>::max() 是 C++ 中标准库 <limits> 中的一个函数，用于获取特定类型的最大值。

在这里，numeric_limits<int>::max() 用于初始化距离数组 dist 中的每个元素为整型的最大值。对于 int 类型，最大值就是 INT_MAX，即整型能够表示的最大正整数。

这样初始化的目的是让初始距离值尽可能大，确保后续更新距离时能够正确比较和取最小值。当最终距离仍然为初始值时，表示没有找到最短路径。

题解 | #【模板】单源最短路1# BFS

全站热榜

创作者周榜