11780. 플로이드 2

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

11780번: 플로이드 2

 

문제 설명

문제 제목처럼 플로이드-워셜 알고리즘을 한 뒤, 경로 추적을 통해 i -> j 로 가는 최소비용의 경로를 출력하는 문제이다.

 

solution

먼저 플로이드-워셜 알고리즘을 통해 최소비용 테이블은 만든다.

i에서 j로 가는 비용을 i -> k -> j 비용으로 갱신할 때, 추적 테이블에 i -> j 갈 때 k를 거쳐간다고 저장한다.

 

void floyd(vvi &dist, vvi &trace)
{
    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (dist[i][j] > dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    trace[i][j] = k;
                }
            }
        }
    }
}

 

최소비용 테이블과 추적 테이블이 다 채워지면 분할정복으로 경로 추적에 들어간다.

startn에서 endn 으로 갈 때, mid를 거쳐서 가므로 startn -> mid 경로를 찾고, mid -> endn 경로를 찾는다.

이 때 pv 벡터에 mid가 두 번 들어가니 중간에 pop_back을 해준다.

 

void find(int startn, int endn, vvi &trace, vi &pv)
{
    int mid = trace[startn][endn];
    if (mid == 0)
    {
        pv.emplace_back(startn);
        pv.emplace_back(endn);
        return;
    }
    find(startn, mid, trace, pv);
    pv.pop_back();
    find(mid, endn, trace, pv);
}

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a, b) (a) ^= (b) ^= (a) ^= (b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
int N, M;
 
void floyd(vvi &dist, vvi &trace)
{
    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (dist[i][j] > dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    trace[i][j] = k;
                }
            }
        }
    }
}
 
void find(int startn, int endn, vvi &trace, vi &pv)
{
    int mid = trace[startn][endn];
    if (mid == 0)
    {
        pv.emplace_back(startn);
        pv.emplace_back(endn);
        return;
    }
    find(startn, mid, trace, pv);
    pv.pop_back();
    find(mid, endn, trace, pv);
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
    vvi dist(N + 1, vector<int>(N + 1, INT_MAX));
    vvi trace(N + 1, vector<int>(N + 1, 0));
 
    int a, b, cost;
    for (int i = 0; i < M; i++)
    {
        cin >> a >> b >> cost;
        dist[a][b] = min(dist[a][b], cost);
    }
    for (int i = 1; i <= N; i++)
        dist[i][i] = 0;
 
    floyd(dist, trace);
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cout << (dist[i][j] >= INT_MAX ? 0 : dist[i][j]) << ' ';
        }
        cout << endl;
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (i == j || dist[i][j] >= INT_MAX)
            {
                cout << 0 << endl;
                continue;
            }
            vector<int> ptrace;
            find(i, j, trace, ptrace);
            cout << ptrace.size() << ' ';
            for (int K : ptrace)
                cout << K << ' ';
            cout << endl;
        }
    }
 
    return 0;
}