11404번: 플로이드

11404번: 플로이드

사용 언어: C++

 

풀이

모든 지점에서 다른 모든 지점으로의 최솟값을 알아야하므로 플로이드 워셜 알고리즘으로 풀어야함.

2차원 배열을 자기 자신은 0, 그 외에는 0x3f (매우 큰 수)로 초기화하고, s도시에서 e도시로 방향이 있고 가중치 w인 AddEdge(s, e, w)로 2차원 배열에 값들 저장.

Run()은 그냥 모든 점들의 최솟값을 확인하는 함수. G[i][j]와 G[i][k] + G[k][j] 중 최솟값을 계속 업데이트. 

#include <bits/stdc++.h>

using namespace std;

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

void Init()
{
    memset(G, 0x3f, sizeof G);

    // 자기 자신 도시는 0
    for (int i = 1; i <= n; i++)
    {
        G[i][i] = 0;
    }
}

// 도시 s -> e, 가중치 w
void AddEdge(int s, int e, int w)
{
    G[s][e] = min(G[s][e], w);  // 같은 경로 버스들 중 최솟값 받기
}

// 모든 시작점으로부터 모든 도착점으로의 최솟값 업데이트 O(V^3)
void Run()
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    Init();

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        AddEdge(a, b, c);
    }

    Run();

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (G[i][j] == 0x3f3f3f3f)
                cout << "0 ";
            else
                cout << G[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}