[알고리즘] 플로이드

구현 방식

• 플로이드 와샬 방식으로 풀되, 처음에 간선 입력을 받을 때 가중치가 최솟값인 걸로 그래프를 채워준다.

#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <limits.h>


using namespace std;

void solution(int N, vector<vector<long long>>& graph);
void FloydWarshall(int N, vector<vector<long long>>& graph);

int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<long long>> graph = vector<vector<long long>>(N + 1, vector<long long>(N + 1, LLONG_MAX));

    for (int i = 1; i <= M; i++)
    {
        int from, to, w;
        cin >> from >> to >> w;
        // 가중치가 최소값인 걸로 그래프를 채워준다.
        graph[from][to] = min(graph[from][to], static_cast<long long>(w));
    }
    for (int i = 1; i <= N; i++)
        graph[i][i] = 0;

    solution(N, graph);
}

void solution(int N, vector<vector<long long>>& graph)
{
    FloydWarshall(N, graph);
    for (int from = 1; from <= N; from++)
    {
        for (int to = 1; to <= N; to++)
        {
            if(graph[from][to] == LLONG_MAX)
                cout << 0 << " ";
            else
                cout << graph[from][to] << " ";
        }
        cout << endl;
    }

}


void FloydWarshall(int N, vector<vector<long long>>& graph)
{
    for (int stopover = 1; stopover <= N; stopover++)
        for(int from = 1; from <= N; from++)
            for(int to = 1; to <= N; to++)
            {
                if (stopover == from || stopover == to)
                    continue;
                if (graph[from][stopover] == LLONG_MAX || graph[stopover][to] == LLONG_MAX)
                    continue;
                graph[from][to] = min(graph[from][to], graph[from][stopover] + graph[stopover][to]);
            }
}