본문으로 바로가기

그래프의 최단 경로는 플로이드-워셜 알고리즘을 이용해 풀 수 있다.

#include <cstdio>

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

void floyd(int);

int main() {
  scanf("%d %d", &n, &m);
  int x, y, z;
  while (m--) {
    scanf("%d %d %d", &x, &y, &z);
    if (!cost[x][y]) {
      cost[x][y] = z;
    } else {
      cost[x][y] = cost[x][y] < z ? cost[x][y] : z;
    }
  }
  floyd(n);
  for (int i=1; i<=n; i++) {
    for (int j=1; j<=n; j++) {
      printf("%d ", cost[i][j]);
    }
    puts("");
  }
  return 0;
}

void floyd(int n) {
  for (int k=1; k<=n; k++) {
    for (int i=1; i<=n; i++) {
      for (int j=1; j<=n; j++) {
        if (i == j) continue;// 시작점과 도착점이 같은 경우
        if (cost[i][k] == 0 || cost[k][j] == 0) continue;// 경유지를 거칠 수 없는 경우
        if (cost[i][j] == 0) {
          cost[i][j] = cost[i][k] + cost[k][j];
        }// i에서 j로 직행할 수 없는 경우
        else if (cost[i][j] > cost[i][k] + cost[k][j]) {
          cost[i][j] = cost[i][k] + cost[k][j];
        }// i에서 j로 k를 경우하는 비용이 더 적다면 갱신
      }
    }
  }
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 2610: 회의준비  (0) 2018.06.14
[BOJ] 1238: 파티  (0) 2018.06.14
[BOJ] 11404: 플로이드  (0) 2018.06.12
[BOJ] 1753: 최단 경로  (0) 2018.06.12
[BOJ] 14621: 나만 안되는 연애  (0) 2018.06.12
[BOJ] 1647: 도시 분할 계획  (0) 2018.06.12

댓글을 달아 주세요