[C++] 11404번 플로이드 - 플로이드-워셜

#include <iostream>
#include <algorithm>

#define MAX_N 101
#define INF 987654321

using namespace std;

int n, m;  //도시의 개수 n, 버스의 개수 m
int map[MAX_N][MAX_N];  //각 도시에서 도시로 가는 최소 비용

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            map[i][j]=INF;  //길이 없음을 표시
    
    for(int i=0; i<m; i++) {
        int u, v, w;  //출발 도시, 도착 도시, 가중치
        
        cin >> u >> v >> w;
        map[u][v]=min(map[u][v], w);
    }
    
    for(int k=1; k<=n; k++) {  //거쳐가는 노드
        for(int i=1; i<=n; i++) {  //출발 노드
            for(int j=1; j<=n; j++) {  //도착 노드
                if(k==i || i==j || k==j)
                    continue;
                if(map[i][k] + map[k][j] < map[i][j])
                    map[i][j]=map[i][k]+map[k][j];
            }
        }
    }
    
    for(int i=1; i<=n; i++, cout << '\n')
        for(int j=1; j<=n; j++)
            cout << (map[i][j]==INF ? 0:map[i][j]) << ' ';
    
    return 0;
}

 

원래 3문제만 풀려고 했는데 어제는 2문제만 올려서 한 문제 더 풀었다. 플로이드-워셜이라는 새로운 알고리즘을 공부해야했는데 솔직히 그 뭐냐 다익스트라 음의 가중치 버전이랑 약간 비슷해서 쉽게 이해했었던 것 같다. 암튼 참고한 사이트는 아래에 있다.

 

 

 

<플로이드-워셜>

https://blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다