[백준 / BOJ] 11404 플로이드

문제

출처 : www.acmicpc.net/problem/11404

11404번: 플로이드

n개의 도시와 m개의 도시를 연결하는 버스의 수가 주어진다.

버스를 타고 이동하는데 일정한 비용이 든다고할때,

a도시에서 b도시까지 가는 최소 비용을 구하는 문제다.

 

풀이

이름에서 알수있듯이 플로이드 와샬 문제다.

 

기본적인 플로이드 와샬문제라서 그냥 플로이드 와샬을 쓰면 풀린다.

한 도시에서 중간도시를 거쳐 다른 도시로 가는 경우가있을수있기때문에, 중간도시를 거쳐가는 경우까지 봐주면된다.

 

도시의 수가 최대 100개라서, 100^3번 반복을 통과할수있다.

 

주의할점이,

 

현실에서 버스는 양방향으로 이동가능하므로 양방향이라 착각할수있는데(내가그랬음), 이 문제에서 버스는 단방향으로 이동가능하다. 

같은 간선이 두번 이상 주어질수있다고 쓰여있다. 예를들어,

1 2 3

1 2 4

1 2 5

이런 1 -> 2 로 가는 버스가 여러개 주어질수있는데, 이때 항상 최솟값으로 간선을 바꿔줘야한다.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/11404%20%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C/main.cpp

devxb/JJUNalgo