[C/C++] 백준 #1956 운동(플로이드 워샬)

이번 문제는 전형적인 플로이드 워샬 문제입니다.

 

플로이드 워샬 알고리즘은 음의 가중치가 있어도 문제를 풀 수 있고, 사이클을 찾아내는데에도 유용합니다.  하지만, 반복횟수가 많기 때문에, 노드의 개수가 많은 경우에는 좋지 않습니다.  알고리즘 시간복잡도가 \(O(V^3)\)입니다.

 

별도의 자료구조가 필요한 것도 아니기 때문에, 알고리즘만 이해하고 있다면, 손쉽게 구현할 수 있습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1956
//        - by Aubrey Choi
//        - created at 2019-11-16
//------------------------------------------------
#include <stdio.h>
#define    INF    1000000000

int main()
{
    int v, e, f, t, w, i, j, k, adj[400][400], min=INF;
    scanf("%d%d",&v,&e);
    for(i=0;i<v;i++) for(j=0;j<v;j++) adj[i][j]=INF;
    while(e--) { scanf("%d%d%d",&f,&t,&w); adj[f-1][t-1]=w; }
    for(k=0;k<v;k++) for(i=0;i<v;i++) for(j=0;j<v;j++)
    {
        if(adj[i][j]>adj[i][k]+adj[k][j]) adj[i][j]=adj[i][k]+adj[k][j];
    }
    for(i=0;i<v;i++) if(adj[i][i]<min) min=adj[i][i];
    printf("%d\n",min<INF?min:-1);
}

 

running