알고리즘/메모
플로이드 와샬
sun__
2019. 8. 18. 17:31
모든 정점간 최단거리를 구해내는 알고리즘
O(V^3)
벨만 포드로 모든 정점간 최단거리를 구하려면 O(V^2 * E) 이므로 벨만포드보다 빠르다.
필요한 것:
dist[MAX][MAX] = {입력값 | 연결안됐으면INF}
for(int k=0; k<n; k++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j];
기본문제
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