반응형
https://www.acmicpc.net/problem/21940
21940번: 가운데에서 만나기
위 조건을 만족하는 도시 X의 번호를 출력한다. 만약 가능한 도시 X가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다.
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/24
[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)
오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk
rudalsd.tistory.com
1. arr[ N ][ N ] 배열을 만들어서 i != j가 아닐 때 값을 987654321로 초기화해줍니다.
2. 플로이드 와샬 알고리즘을 이용하여 각 도시 간의 거리를 저장합니다.
3. 1부터 N까지 for문을 통해 돌면서 각 도시별로 arr[ i ][ C[ j ] ] + arr[ C[ j ] ][ i ] 중 최댓값을 저장합니다.
4. 최댓값 중 최솟값을 ans에 push 합니다.
5. 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 56 57 58 59 60 61 62 63 64 65 | #include<iostream> #include<vector> using namespace std; int N, M, K; int arr[201][201]; int C[201]; vector<int> ans; 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, T; scanf("%d %d %d", &A, &B, &T); arr[A][B] = T; } 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) { arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]); } } } } scanf("%d", &K); for (int i = 0; i < K; i++) { scanf("%d", &C[i]); } int min = 987654321; for (int i = 1; i <= N; i++) { int Max = 0; for (int j = 0; j < K; j++) { Max = max(Max, arr[i][C[j]] + arr[C[j]][i]); } if (min > Max) { min = Max; ans.clear(); ans.push_back(i); } else if (min == Max) { ans.push_back(i); } } for (auto& next : ans) { printf("%d ", next); } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 23286번 - 허들 넘기 (C++) (0) | 2023.03.25 |
|---|---|
| [ 백준 ] 15422번 - Bumped! (C++) (0) | 2023.03.24 |
| [ 백준 ] 14567번 - 선수과목 (Prerequisite) (C++) (0) | 2023.03.22 |
| [ 백준 ] 4963번 - 섬의 개 (C++) (0) | 2023.03.21 |
| [ 백준 ] 10723번 - 판게아 1 (C++) (0) | 2023.03.20 |