Comment

徐鹏: 2024-11-21 20:59:56

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

using namespace std;

// 使用Floyd-Warshall算法计算最短路径
void floydWarshall(const vector<vector<int>>& graph, vector<vector<int>>& dist) {
    int V = graph.size(); // 顶点数

    // 初始化距离矩阵
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            dist[i][j] = (graph[i][j] != -1) ? graph[i][j] : -1;
        }
    }

    for (int i = 0; i < V; ++i) {
        dist[i][i] = 0;
    }

    // Floyd-Warshall算法核心部分
    for (int k = 0; k < V; ++k) { // 中间顶点
        for (int i = 0; i < V; ++i) { // 起始顶点
            for (int j = 0; j < V; ++j) { // 目标顶点
                if (dist[i][k] != -1 && dist[k][j] != -1 && dist[i][k] + dist[k][j] < (dist[i][j] != -1 ? dist[i][j] : INT_MAX)) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<vector<int>> graph(n, vector<int>(n));
        vector<vector<int>> dist(n, vector<int>(n, -1));

        // 输入距离矩阵
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> graph[i][j];
                if (i == j) {
                    dist[i][j] = 0; // 对角线为0，表示自身到自身的距离为0
                }
            }
        }

        // 调用Floyd-Warshall算法
        floydWarshall(graph, dist);

        // 输出结果
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cout << dist[i][j] << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

Huhu_Miao: 2024-11-17 14:57:24

/**
 *    author:  Huhu_Miao
 *    created: 2024.11.17 14:56:00 (UTC+8)
**/
#include<bits/stdc++.h>

void solve(){
	int n;
	std::cin >> n;
	std::vector<std::vector<int>> d(n,std::vector<int>(n,0));
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < n; j++){
			int val;
			std::cin >> val;
			d[i][j] = (val==-1) ?100000 : val;
		}
	}

	for(int k = 0 ; k < n ; k++)
		for(int i = 0 ; i < n ; i++)
			for(int j = 0 ; j < n ; j++)
				d[i][j] = std::min(d[i][k]+d[k][j],d[i][j]);

	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < n ; j++){
			std::cout << ((d[i][j] >= 100000) ? -1 : d[i][j]) << ' ';
		}
		std::cout << '\n';
	}
}

int main(){
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
	int T; std::cin>>T;
	while(T--) solve();
	return 0;
}

61520218: 2021-06-14 16:34:02

裂开