[백준] 11404. 플로이드

남혁준 2020. 5. 1. 17:06

https://www.acmicpc.net/problem/11404

11404번: 플로이드

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작

www.acmicpc.net

플로이드 와샬 알고리즘 문제였습니다.

'시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.'

이와같이 두 정점사이에 노선이 여러개 이므로 우선, 입력단계에서 비용을 최소값으로 세팅을 해줘야 합니다.

이후 과정은 무한대 값만 10000000 으로 해주고

플로이드 와샬 알고리즘을 구현하면 됩니다.