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

邻接表与邻接矩阵空间复杂度直观差异

邻接表 空间复杂度 O(N+M) 邻接矩阵 空间复杂度O(N*N)

//邻接表
#include <bits/stdc++.h>
using namespace std;

const int N = 5001;

int bfs(int n, vector<vector<int>>& adj) {
    int d[N];
    memset(d, -1, sizeof(d)); //记录1到每个点的距离，-1表示未访问。
    int start = 1; //起点为1号
    d[start] = 0; //1到1距离为0
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        start = q.front(); //取队头结点
        q.pop();//取完出队

        for (int i = 0; i < adj[start].size(); i++) {
            int curNode = adj[start][i];
            if (d[curNode] == -1) {
                d[curNode] = d[start] + 1;
                if (curNode == n) return d[curNode]; //若到达n号 返回距离
                q.push(curNode);
            }
        }
    }
    return -1;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(N);//邻接表
    for (int c = 0; c < m; c++) {
        int i, j;
        cin >> i >> j;
        adj[i].push_back(j);
        adj[j].push_back(i);
    }
    int dist = bfs(n, adj);
    cout << dist;
    return 0;
}

//邻接矩阵
#include <bits/stdc++.h>
using namespace std;

const int N = 5001;

int bfs(int n, vector<vector<int>>& adj) {
    int d[N];
    memset(d, -1, sizeof(d)); //记录1到每个点的距离，-1表示未访问。
    queue<int> q;
    int start = 1;
    d[start] = 0;
    q.push(start);
    while (!q.empty()) {
        start = q.front();
        q.pop();
        
        for (int pos = 0; pos < N; pos ++) {
            if (adj[start][pos] == 1 && d[pos] == -1) {
                d[pos] = d[start] + 1;
                if (pos == n) return d[pos];
                q.push(pos);
            }
        }
    }
    return -1;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj;
    adj.resize(N, vector<int>(N, 0));//邻接矩阵
    for (int c = 0; c < m; c++) {
        int i, j;
        cin >> i >> j;
        adj[i][j] = 1;
        adj[j][i] = 1;
    }
    int dist = bfs(n, adj);
    cout << dist;
    return 0;
}