백준
백준 소스코드 [C++] 11404 플로이드
Hani_Levenshtein
2020. 8. 29. 10:14
https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 �
www.acmicpc.net
백준 소스코드 [C++] 11404 플로이드
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
typedef long long ll;
using namespace std;
int arr[100][100];
int n,m,s,d,w;
void init() {
for (int i = 0;i < n;i++)
for (int j = 0;j < n;j++)
if (i != j)arr[i][j] = 987654321;
else arr[i][j] = 0;
}
void floyd() {
for (int via = 0;via < n;via++)
for (int start = 0;start < n;start++) {
if (arr[start][via] == 987654321) continue;
for (int dest = 0;dest < n;dest++)
if (arr[start][dest] > arr[start][via] + arr[via][dest])
arr[start][dest] = arr[start][via] + arr[via][dest];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
cin >> m;
init();
for (int i = 0; i < m;i++) {
cin >> s >> d >> w;
arr[s-1][d-1] = min(arr[s - 1][d - 1],w);
}
floyd();
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (arr[i][j]==987654321) cout << "0 ";
else cout << arr[i][j] << " ";
}
cout << '\n';
}
return 0;
}