[C++] 백준 11404번 플로이드

각각의 거리에 대한 최단거리를 구하는 문제입니다.

a, b, c 있다면

a -> b

a -> c

b -> a

b -> c

c -> a

c -> b

를 구하는 문제입니다.

모든 노드쌍에 대한 최단거리를 구할 때는 플로이드-워셜 알고리즘을 사용합니다.

반복문을 3번 이용해서 구현할 수 있습니다.

 

#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;

int d[101][101];
int n, m;

void Init()
{
  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      d[i][j] = INF;
    }
  }
}

void Floyd()
{
  for (int m = 1; m <= n; m++)
  {
    for (int s = 1; s <= n; s++)
    {
      for (int e = 1; e <= n; e++)
      {
        if (d[s][m] != INF && d[m][e] != INF)
        {
          d[s][e] = min(d[s][e], d[s][m] + d[m][e]);
        }
      }
    }
  }
}

int main(int argc, char *argv[])
{
  cin >> n;
  cin >> m;
  Init();
  for (int i = 0; i < m; i++)
  {
    int x, y, c;
    cin >> x;
    cin >> y;
    cin >> c;
    if (d[x][y] > c)
    {
      d[x][y] = c;
    }
  }
  Floyd();

  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      if (i == j || d[i][j] == INF)
      {
        cout << "0 ";
      }
      else
      {
        cout << d[i][j] << " ";
      }
    }
    cout << endl;
  }
  return 0;
}