반응형
https://www.acmicpc.net/problem/1719
1719번: 택배
첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/24
[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)
오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk
rudalsd.tistory.com
1. arr[ n ][ n ] 배열을 만들어 각 노드까지의 거리를 저장해 줍니다.
2. ans[ n ][ n ] 배열을 만들어 각 노드까지 갈 때 가장 처음으로 거치는 노드를 저장해 줍니다.
3. 플로이드 와샬 알고리즘을 이용하여 각 노드 간의 최단거리를 저장해 주고, 최단거리를 갱신할 때 ans[ j ][ k ] = ans[ j ][ i ]를 같이 처리해 줍니다.
4. ans 배열을 출력합니다.
[ 소스코드 ]
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include<iostream> using namespace std; int n, m; int arr[201][201]; int ans[201][201]; int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i != j) { arr[i][j] = 987654321; } } } for (int i = 0; i < m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); ans[a][b] = b; ans[b][a] = a; arr[a][b] = c; arr[b][a] = c; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { if (arr[j][i] != 0 && arr[i][k] != 0) { if (arr[j][k] > arr[j][i] + arr[i][k]) { arr[j][k] = arr[j][i] + arr[i][k]; ans[j][k] = ans[j][i]; } } } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) { printf("- "); } else { printf("%d ", ans[i][j]); } } printf("\n"); } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 14728번 - 벼락치기 (C++) (0) | 2023.04.03 |
|---|---|
| [ 백준 ] 13424번 - 비밀 모임 (C++) (0) | 2023.04.02 |
| [ 백준 ] 13023번 - ABCDE (C++) (0) | 2023.03.31 |
| [ 백준 ] 17490번 - 일감호에 다리 놓기 (C++) (0) | 2023.03.30 |
| [ 백준 ] 14921번 - 용액 합성하기 (C++) (0) | 2023.03.29 |