IPST58: Restaurant

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int N = 300 + 5;

int mat[N][N], dist[N], par[N], idx[N], deg[N];

int main(){

    int nVertex, cmd;
    scanf("%d%d", &nVertex, &cmd);
    for(int u = 1; u <= nVertex; ++u){
        for(int v = 1; v <= nVertex; ++v){
            scanf("%d", &mat[u][v]);
        }
        idx[u] = u;
        dist[u] = 1e9;
    }

    dist[1] = 0;
    par[1] = 0;
    for(int i = 0; i < nVertex; ++i){
        int mn = 1e9;
        int u = 0;
        for(int j = 1; j <= nVertex - i; ++j){
            if(dist[j] < mn){
                mn = dist[j];
                u = j;
            }
        }
        if(par[u] != 0){
            ++deg[idx[u]];
            ++deg[par[u]];
        }
        for(int v = 1; v <= nVertex - i; ++v){
            if(u == v){
                continue;
            }
            if(mat[idx[u]][idx[v]] < dist[v]){
                dist[v] = mat[idx[u]][idx[v]];
                par[v] = idx[u];
            }
        }
        swap(idx[u], idx[nVertex - i]);
        swap(dist[u], dist[nVertex - i]);
        swap(par[u], par[nVertex - i]);
    }

    for(int i = 1; i <= nVertex; ++i){
        if(deg[i] >= 3){
            cout << i << '\n';
            if(cmd == 2){
                cout << deg[i];
            }
        }
    }

    return 0;
}