반응형
문제 출처 :
https://www.acmicpc.net/problem/11404
알고리즘 분석 :
문제 해결에 필요한 사항
1. 플로이드 워셜 알고리즘 :: http://www.crocus.co.kr/search/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C
플로이드 워셜 알고리즘의 기초가 되는 소스 코드이다.
adj를 i == j인 부분은 최단거리가 0(자기 자신), 그 외에는 INF로 해주고
입력 부분에서 입력을 받은 후
3중 for문을 통해 플로이드 워셜 알고리즘을 실행한다.
이때 플로이드를 이용할 수 있는 이유는 n <= 100이기 때문이다.
소스 코드 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include <iostream> #include <cstdio> #define INF 987654321 #define min(a,b)(a < b ? a : b) using namespace std; int adj[101][101]; int dist[101][101]; int main() { int V, E; scanf("%d %d", &V, &E); for (int i = 1; i <= V; i++) for (int j = 1; j <= V; j++) i == j ? adj[i][j] = 0 : adj[i][j] = INF; for (int i = 0; i < E; i++) { int from, to, val; scanf("%d %d %d", &from, &to, &val); adj[from][to] = min(adj[from][to], val); } for (int k = 1; k <= V; k++) for (int x = 1; x <= V; x++) for(int y = 1; y <= V; y++) if (adj[x][y] > adj[x][k] + adj[k][y]) adj[x][y] = adj[x][k] + adj[k][y]; for (int i = 1; i <= V; i++) { for (int j = 1; j <= V; j++) printf("%d ", adj[i][j] == INF ? 0 : adj[i][j]); printf("\n"); } return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[2240번] 자두 나무 (2) | 2017.04.13 |
---|---|
[3048번] 개미 (0) | 2017.04.13 |
[8979번] 올림픽 (0) | 2017.04.12 |
[10868번] 최소값 (0) | 2017.04.12 |
[2414번] 게시판 구멍 막기 (0) | 2017.04.12 |