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

www.acmicpc.net/problem/11780

11780번: 플로이드 2

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

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#include <cstdlib>
#include <list>
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define pli pair<ll, int>
#define make_unique(v) sort(all(v)), v.erase(unique(all(v), v.end())
typedef long long ll;
using namespace std;



int n,m;
ll arr[100][100];
vector<ll> path[100][100];
ll MAX =LONG_LONG_MAX-200000;
void floyd() {
    for (int via = 0;via < n;via++)
        for (int here = 0;here < n;here++) {
            if (arr[here][via] == MAX) continue;
            for (int next = 0;next < n;next++) {
                if (arr[here][next] > arr[here][via] + arr[via][next]) {
                    arr[here][next] = arr[here][via] + arr[via][next];
                    path[here][next] = path[here][via];
                    path[here][next].pop_back();
                    path[here][next].insert(path[here][next].end(), all(path[via][next]));
                }
            }
        }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    cin >> m;
    for (int i = 0;i < n;i++)
        for (int j = 0;j < n;j++)
            if (i == j) arr[i][j] = 0;
            else arr[i][j] = MAX;

    for (int i = 0;i < m;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (arr[u - 1][v - 1] > w) {
            arr[u - 1][v - 1] = w;
            path[u - 1][v - 1].clear();
            path[u - 1][v - 1].push_back(u - 1);
            path[u - 1][v - 1].push_back(v - 1);
        }
    }

    floyd();

    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++)
        if (arr[i][j]==MAX) cout<<"0 ";
        else cout << arr[i][j] << " ";
        cout << '\n';
    }

    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {

            if (path[i][j].size() == 0) cout << "0";
            else{
                cout << path[i][j].size() << " ";
                for (auto a : path[i][j]) cout << a+1 << " ";
            }
            cout << '\n';
        }
    }

    return 0;
}