백준 11780번 플로이드2

백준 11780 플로이드2

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MAX = 101;
 
int n, m;
int city[MAX][MAX];
int travel[MAX][MAX];
int Path[MAX][MAX];
int Count;
 
void route(int i, int j) {
    if (Path[i][j] != 0) {
        route(i, Path[i][j]);
        cout << Path[i][j] << " ";
        route(Path[i][j], j);
    }
}
 
void Findcost(int i, int j) {
    if (Path[i][j] != 0) {
        Count++;
        Findcost(i, Path[i][j]);
        Findcost(Path[i][j], j);
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b,cost;
        cin >> a >> b >> cost;
        if (city[a][b] == 0)
            city[a][b] = cost;
        else
            city[a][b] = min(city[a][b], cost);
    }
    for(int k=1;k<=n;k++)
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                //경로가 둘중 하나라도 없는경우, 자기가 자신한테 가는경우 모두 제외
                if (city[i][k]==0||city[k][j] == 0 || i == j)
                    continue;
                //직선으로 가는 경우가 없는경우,우회해서 가는게 더 빠른경우 갱신
                if (city[i][j]==0||city[i][j] > city[i][k] + city[k][j]) {
                    city[i][j] = city[i][k] + city[k][j];
                    Path[i][j] = k;
                }
            }
        }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << city[i][j] << " ";
        cout << endl;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (city[i][j] == 0) {
                cout << 0 << endl;
            }
            else {
                //시작,끝은 무조건 지나므로 2개 시작
                Count = 2;
                //도시 몇번지나는지 카운터해주기
                Findcost(i, j);
                cout << Count<< " " << i<<" ";
                route(i,j);
                cout << j<<endl;
 
            }
        }
    }
    return 0;
}
 

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

Path[i][j]에 경로 k를 넣은뒤 재귀를 이용해서 route.Findcost함수를 작성하는게 포인트였습니다.

Findcost함수의 Count++의 위치는 전,중,후 아무곳이나 상관없이 카운트를 할 수 있습니다.