반응형
https://www.acmicpc.net/problem/11265
11265번: 끝나지 않는 파티
입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/24
[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)
오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk
rudalsd.tistory.com
1. arr[ N ][ N ] 배열을 만들어서 값을 입력받습니다.
2. 플로이드 와샬 알고리즘을 이용하여 각 구간까지의 최단거리를 갱신해줍니다.
3. arr[ A ][ B ]의 값이 C보다 크다면 Stay here을 출력하고 아니라면 Enjoy other party를 출력합니다.
[ 소스코드 ]
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 | #include<iostream> using namespace std; int N, M; int arr[501][501]; int main() { scanf("%d %d", &N, &M); 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++) { arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]); } } } for (int i = 0; i < M; i++) { int A, B, C; scanf("%d %d %d", &A, &B, &C); if (arr[A][B] > C) { printf("Stay here\n"); } else { printf("Enjoy other party\n"); } } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 17490번 - 일감호에 다리 놓기 (C++) (0) | 2023.03.30 |
|---|---|
| [ 백준 ] 14921번 - 용액 합성하기 (C++) (0) | 2023.03.29 |
| [ 백준 ] 1781번 - 컵라면 (C++) (0) | 2023.03.27 |
| [ 백준 ] 15989번 - 1, 2, 3 더하기 4 (C++) (0) | 2023.03.26 |
| [ 백준 ] 23286번 - 허들 넘기 (C++) (0) | 2023.03.25 |