백준 11404번 플로이드

문제 링크입니다: https://www.acmicpc.net/problem/11404

플로이드 알고리즘을 사용하면 쉽게 풀리는 문제였습니다.

정식 명칭이 플로이드-와샬 알고리즘인 것은 오늘 처음 알았네요.

간단하게 플로이드 알고리즘을 설명하자면 from에서 to로 곧장 가는 것보다 via를 통해 가는 것이 더 빠를 경우를 찾는 알고리즘입니다.

코드를 보면 쉽게 이해할 수 있을 것입니다!(실행속도 향상을 위해 중간 중간 continue문을 넣었습니다.)

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 100 + 1;

const int INF = 100000 + 1;

 

int N, M;

int graph[MAX][MAX];

 

void floyd(void)

{

        //via번째 도시를 거쳐가는게 더 빠를 경우 update

        for (int via = 1; via <= N; via++)

        {

                 for (int from = 1; from <= N; from++)

                 {

                         if (graph[from][via] == 0)

                                 continue;

 

                         for (int to = 1; to <= N; to++)

                         {

                                 if (graph[via][to] == 0 || from == to)

                                          continue;

 

                                 if (graph[from][to] == 0 || graph[from][to] > graph[from][via] + graph[via][to])

                                          graph[from][to] = graph[from][via] + graph[via][to];

                         }

                 }

        }

}

 

int main(void)

{

        cin >> N >> M;

 

        for (int i = 0; i < M; i++)

        {

                 int from, to, cost;

                 cin >> from >> to >> cost;

                

                 if (!graph[from][to])

                         graph[from][to] = cost;

                 else //이미 경로가 있는 경우 최소값 선택

                         graph[from][to] = min(graph[from][to], cost);

        }

 

        floyd();

 

        for (int i = 1; i <= N; i++)

        {

                 for (int j = 1; j <= N; j++)

                         cout << graph[i][j] << " ";

                 cout << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~