백준_플로이드

[ 해결 방법 ]

제목처럼 플로이드 와셜 알고리즘을 이용해서 풀면된다. 줄여서 플로이드 알고리즘은 다이나믹 프로그래밍을 이용해서 모든 노드간의 최단거리를 구하는 알고리즘이다.

다이나믹 프로그래밍을 구현하기 위한 점화식은 dp[i][j] = dp[i][k] + dp[k][j] 이다.

여기서 i는 시작 노드, j는 도착 노드, k는 경유할 노드이다.

i노드에서 k노드를 경유해서 j노드로 가는 경로가 i노드에서 j로 바로 가는 경로보다 짧으면 위의 점화식을 적용하면 된다.

문제에서 경로정보 중에 불필요한 정보가 들어온다.

3 5 1로 들어온 입력 데이터가 나중에 3 5 10으로 들어올 때도 있다. 이 것만 걸러서 플로이드 와셜 알고리즘을 작성해주면 된다.

[ 코드 ]

#include <iostream>
#define MAX 101
#define INF 999999999999999999
using namespace std;
  
int n, m;
long long dp[MAX][MAX];
  
void InData()
{
    cin >> n;
    cin >> m;
      
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i != j)
                dp[i][j] = INF;
        }
    }
      
    int from, to, cost;
    for(int i = 0; i < m; i++)
    {
        cin >> from >> to >> cost;
        if(dp[from][to] > cost)
            dp[from][to] = cost;
    }
}
  
int main() 
{
    InData();
      
    for(int k = 1; k <= n; k++)  // pass stop
    {
        for(int i = 1; i <= n; i++)  // from
        {
            for(int j = 1; j <= n; j++)  // to
            {
                if(dp[i][j] > dp[i][k] + dp[k][j])
                    dp[i][j] = dp[i][k] + dp[k][j];
            }
        }
    }
      
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(dp[i][j] == INF) dp[i][j] = 0;
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}