11404 플로이드

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

11404번: 플로이드

플로이드-와샬 알고리즘 기본 문제.

 

플로이드-와샬 알고리즘은 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘이다.

 

플로이드-와샬 알고리즘의 핵심 아이디어는 '거쳐가는 정점'을 기준으로 최단거리는 구하는 것이다.

i 정점으로부터 j 정점으로 갈 때, k정점을 지나서 가는 경로가 더 빠른지, 다른 경로 빠른지 구하면 된다.

 

DP적인 성격을 띄며 어떤 경로가 지금까지 확인해본 경로보다 가깝다면, 경로 비용(더 빠름)을 갱신한다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> city(n+1, vector<int>(n+1, (int)1e9));
    for(int i=1;i<=n;i++)
        city[i][i] = 0;
 
    int s, e, c;
    for(int i=0;i<m;i++)
    {
        cin >> s >> e >> c;
        city[s][e] = min(city[s][e], c);
    }
 
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(city[i][j] > city[i][k]+city[k][j])
                    city[i][j] = city[i][k]+city[k][j];
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(city[i][j] >= (int)1e9) cout << 0 << ' ';
            else cout << city[i][j] << ' ';
        }
        cout << endl;
    }
 
    return 0;
}