[백준 / C++] 1956번: 운동 (플로이드 워셜 알고리즘)

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 난이도: solved.ac 골드 4 알고리즘 분류 그래프 이론, 플로이드 워셜 (Floyd-Warshall) 접근 방법 다익스트라 알고리즘을 이용할 수도 있겠지만 정점의 개수가 적으므로 플로이드 워셜 알고리즘을 이용하였다. 구현 기존의 플로이드 워셜 문제에서는 자기 자신으로 가는 비용은 0으로 초기화했지만, 이 문제에서는 자기 자신을 포함한 모든 노드로 가는 비용..

• format_list_bulleted PS/백준
• · 2023. 7. 13.
• textsms

[백준 / C++] 11404번: 플로이드 (플로이드 와샬 알고리즘 - Floyd Warshall Algorithm)

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 이론, 플로이드 워셜(Floyd-Warshall) 접근 방법 플로이드 워셜 (플로이드 와샬) 알고리즘을 그대로 구현하면 되는 문제다 자기 자신으로의 가는 비용은 0으로 두고, 자기 자신을 제외한 나머지 모든 노드로 가는 비용은 INF(가장 큰 수)로 둔다 그리고 점화식을 이용해 다른 노드로 가는데 드는 최소 비용을 계산한다 코드 #inclu..

• format_list_bulleted PS/백준
• · 2023. 7. 13.
• textsms