반응형
https://www.acmicpc.net/problem/1956
1956번: 운동
첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의
www.acmicpc.net
[ 문제풀이 ]
문제를 풀기 전 다음 글을 먼저 읽고 오시는 것을 추천드립니다!
https://rudalsd.tistory.com/24?category=1064608
[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)
오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이
rudalsd.tistory.com
1. 플로이드 와샬을 이용하여 각 마을까지의 최단거리를 저장합니다.
2. 1번 마을에서 1번 마을까지 거리부터 V번 마을에서 V번 마을까지 거리까지 최솟값을 비교해 ans에 저장합니다.
3. 만약 ans 값이 987654321이라면 -1을 출력하고, 아니라면 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 | #include<iostream> using namespace std; int V, E; int arr[401][401]; int main() { scanf("%d %d", &V, &E); for (int i = 1; i <= V; i++) { for (int j = 1; j <= V; j++) { arr[i][j] = 987654321; } } for (int i = 0; i < E; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); arr[a][b] = c; } for (int i = 1; i <= V; i++) { //플로이드 와샬 for (int j = 1; j <= V; j++) { for (int k = 1; k <= V; k++) { if (arr[j][k] > arr[j][i] + arr[i][k]) { arr[j][k] = arr[j][i] + arr[i][k]; } } } } int ans = 987654321; for (int i = 1; i <= V; i++) { //사이클의 최소 길이 ans = min(ans, arr[i][i]); } if (ans == 987654321) { ans = -1; } printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
[ 백준 ] 14442번 - 벽 부수고 이동하기 2 (C++) (0) | 2022.10.13 |
---|---|
[ 백준 ] 17472번 - 다리 만들기 2 (C++) (0) | 2022.10.12 |
[ 백준 ] 23291번 - 어항 정리 (C++) (0) | 2022.10.10 |
[ 백준 ] 5014번 - 스타트링크 (C++) (0) | 2022.10.09 |
[ 백준 ] 17406번 - 배열 돌리기 4 (C++) (0) | 2022.10.08 |