[C++] 백준 11780 플로이드 2

 

#include <iostream>
#include <vector>
#include <algorithm>
 
#define MAX 10000001
using namespace std;
 
int arr[101][101];
int mid[101][101];
 
int main() 
{
    int n, m;
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            arr[i][j] = MAX;
        }
    }
 
    for (int i = 0; i < m; ++i)
    {
        int start, end, cost;
        cin >> start >> end >> cost;
 
        arr[start][end] = min(arr[start][end], cost);
        mid[start][end] = end;
    }
 
    for (int z = 1; z <= n; ++z)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (i == j) 
                    continue;
 
                if (arr[i][j] > arr[i][z] + arr[z][j])
                {
                    arr[i][j] = arr[i][z] + arr[z][j];
                    mid[i][j] = mid[i][z];
                }
            }
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (arr[i][j] == MAX) 
                cout << "0 ";
 
            else 
                cout << arr[i][j] << " ";
        }
 
        cout << "\n";
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (arr[i][j] == MAX)
            {
                cout << "0\n";
                continue;
            }
 
            vector<int> vec;
            int now = i;
 
            while (now != j) 
            {
                vec.push_back(now);
                now = mid[now][j];
            }
 
            vec.push_back(now);
 
            cout << vec.size() << ' ';
 
            for (int now : vec)
            {
                cout << now << ' ';
            }
 
            cout << '\n';
        }
    }
 
    return 0;
}

플로이드 와샬 문제라서 i,j,z로 회전하면서 최저의 길이를 구합니다.

하지만 이 문제는 최저의 길이의 중간 도착지를 알아야 하기 때문에

플로이드와샬을 알고리즘을 실행하면서 더 작은 길이가 있다면 중간점을 따로 저장합니다.

중간점을 계속해서 들어가면서 현재점까지 찾아옵니다.