플로이드
📌문제n개의 도시가 있고, 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하시오. 📌풀이도시 A에서 B로 가는 간선이 여러개일 경우 비용이 짧은 간선만 고려초기에 간선 정보를 입력받을 때 가장 짧은 간선 정보만 저장한 후 플로이드 워셜 알고리즘 수행 📌코드INF = int(1e9) # 무한# 노드의 개수, 간선의 개수 입력n = int(input())m = int(input())# 2차원 리스트(그래프)를 만들고 무한으로 초기화graph = [[INF] * (n + 1) for _ in range(n + 1)]# 자기 자신에서 자기 자신으로 가는 비용 0f..
코딩테스트
2024. 12. 22. 19:24