T547128 图的最短路径 题解

bilibili_daogu · 2025-01-24 18:32:52 · 题解

c++:

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

using namespace std;

vector<int> shortestPath(const vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<int> distances(n, INT_MAX); // 初始化距离为无穷大
    distances[start] = 0; // 起始节点到自身的距离为0

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

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

        for (int neighbor = 0; neighbor < n; ++neighbor) {
            if (graph[node][neighbor] == 1 && distances[neighbor] == INT_MAX) {
                // 如果存在边且尚未被访问
                distances[neighbor] = distances[node] + 1; // 更新距离
                q.push(neighbor); // 将邻居加入队列
            }
        }
    }

    // 将无法到达的节点的距离设置为-1
    for (int i = 0; i < n; ++i) {
        if (distances[i] == INT_MAX) {
            distances[i] = -1;
        }
    }

    return distances;
}

int main() {
    int n;
    cin >> n; // 读入图的节点数
    vector<vector<int>> graph(n, vector<int>(n));

    // 读入邻接矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> graph[i][j];
        }
    }

    int start;
    cin >> start; // 读入起始节点编号

    // 计算最短路径
    vector<int> distances = shortestPath(graph, start);

    // 输出结果
    for (int i = 0; i < distances.size(); ++i) {
        if (i > 0) cout << " "; // 格式化输出
        cout << distances[i];
    }
    cout << endl;
    system("pause");
    return 0;
}