백준 11404번 플로이드

백준 11404번 플로이드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MAX = 101;
 
int n, m;
int city[MAX][MAX];
int travel[MAX][MAX];
int Path[MAX][MAX];
 
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    
    for (int i = 1; i <= m; i++) {
        int a, b,cost;
        cin >> a >> b >> cost;
        if (city[a][b] == 0)
            city[a][b] = cost;
        else
            city[a][b] = min(city[a][b], cost);
    }
    for(int k=1;k<=n;k++)
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                //경로가 둘중 하나라도 없는경우, 자기가 자신한테 가는경우 모두 제외
                if (city[i][k]==0||city[k][j] == 0 || i == j)
                    continue;
                //직선으로 가는 경우가 없는경우,우회해서 가는게 더 빠른경우 갱신
                if (city[i][j]==0||city[i][j] > city[i][k] + city[k][j]) {
                    city[i][j] = city[i][k] + city[k][j];
                    Path[i][j] = k;
                }
            }
        }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << city[i][j] << " ";
        cout << endl;
    }
 
    return 0;
}
 

출처:https://www.acmicpc.net/problem/11404

플로이드의 최단경로 알고리즘을 사용하는 문제였습니다. 

city[i][j]==0인 경우가 최소값으로 들어가는게 아니라 길이 없다는 예외처리를 해주는 것에 신경을 쓰면 풀 수 있는 문제였습니다.