반응형
https://www.acmicpc.net/problem/1507
1507번: 궁금한 민호
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/24
[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)
오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk
rudalsd.tistory.com
1. arr[ N ][ N ] 배열을 만들어 각 노드까지의 거리를 저장해 줍니다.
2. 플로이드 와샬 알고리즘을 이용하여 최단거리가 갱신되면 -1을 출력하고, 해당 노드 간의 거리가 두 간선의 길이의 합과 같다면 두 간선을 ans 배열에 따로 저장해 줍니다.
3. 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 | #include<iostream> using namespace std; int N; int arr[21][21]; int ans[21][21]; int main() { scanf("%d", &N); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { scanf("%d", &arr[i][j]); } } for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { for (int k = 1; k <= N; k++) { if (arr[j][k] > arr[j][i] + arr[i][k]) { printf("-1"); return 0; } else if (arr[j][k] == arr[j][i] + arr[i][k]) { if (ans[j][k] != -1 && ans[j][i] != -1 && ans[i][k] != -1) { ans[j][k] = -1; ans[j][i] = arr[j][i]; ans[i][k] = arr[i][k]; } } } } } int ret = 0; for (int i = 1; i < N; i++) { for (int j = i+1; j <= N; j++) { if (ans[i][j] != -1) { ret += ans[i][j]; } } } printf("%d", ret); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2032번 - 신기한 소수 (C++) (0) | 2023.04.19 |
|---|---|
| [ 백준 ] 2602번 - 돌다리 건너기 (C++) (0) | 2023.04.18 |
| [ 백준 ] 2668번 - 숫자고르기 (C++) (0) | 2023.04.16 |
| [ 백준 ] 1253번 - 좋다 (C++) (0) | 2023.04.15 |
| [ 백준 ] 2749번 - 피보나치 수 3 (C++) (0) | 2023.04.14 |