Floyd-Warshall algorithm
user_3763047219
c_cpp
3 years ago
1.5 kB
5
Indexable
#include <iostream> int main() { int n = 0, m = 0; static int E[201][2] = {}; static float w[201][3] = {}; scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d %d %f %f", &E[i][0], &E[i][1], &w[i][0], &w[i][1]); } for (int i = 1; i <= m; i++) {//m if (w[i][0] > w[i][1]) { w[i][2] = w[i][0] - w[i][1]; } else { w[i][2] = w[i][1] - w[i][0]; } } static float c[51][51] = {};//造一個點對點的矩陣 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) { c[i][j] = 0; } else { c[i][j] = 999999; } } } for (int i = 1; i <= m; i++) {//把已有的權重放進矩陣 c[E[i][0]][E[i][1]] = w[i][2]; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i != j) {//相等不用做 if (c[i][j] > c[i][k] + c[k][j]) { c[i][j] = c[i][k] + c[k][j]; } } } } } for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { if (c[i][j] == 999999) { std::cout << "N" << " "; } else { std::cout << c[i][j] << " "; } } if (c[i][n] == 999999) { std::cout << "N" ; } else { std::cout << c[i][n] ; } std::cout << "\n"; } for (int j = 1; j < n; j++) { if (c[n][j] == 999999) { std::cout << "N" << " "; } else { std::cout << c[n][j] << " "; } } if (c[n][n] == 999999) { std::cout << "N" ; } else { std::cout << c[n][n] ; } }
Editor is loading...