반응형
https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작
www.acmicpc.net
본 문제는 제목을 통해 알 수 있다. 바로 플로이드 와샬 알고리즘을 이용해서 푸는 문제다. 플로이드 와샬 알고리즘은 간단하다.
|
1
2
3
4
5
6
7
8
|
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if (d[i][j] > d[i][k] + d[k][j]) d[i][j] = d[i][k] + d[k][j];
}
}
}
|
cs |
이게 끝이다. O(n^3) 방법이다. 문제에서 자신을 연결하는 경우는 없다고 하여 4번 줄에서 예외처리 했다.
전체 코드는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <cstdio>
#include <vector>
using namespace std;
int d[101][101];
int main() {
int n, m;
scanf("%d %d", &n, &m);
vector<pair<int, int>> v[101];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) d[i][j] = 0;
else d[i][j] = 1e9;
}
}
for (int i = 0; i < m; i++) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
if (d[x][y] > z) d[x][y] = z;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if (d[i][j] > d[i][k] + d[k][j]) d[i][j] = d[i][k] + d[k][j];
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (d[i][j] == 1e9) printf("0 ");
else printf("%d ", d[i][j]);
}
printf("\n");
}
printf("\n");
}
|
cs |
반응형
'백준' 카테고리의 다른 글
| [백준 2573] 빙산, C++ (0) | 2020.02.25 |
|---|---|
| [백준 10868] 최솟값, C++ (0) | 2020.02.21 |
| [백준 1916] 최소비용 구하기, C++ (0) | 2020.02.21 |
| [백준 14891] 톱니바퀴, C++ (0) | 2020.02.20 |
| [백준 17144] 미세먼지 안녕!, C++ (0) | 2020.02.19 |
댓글