Submission

Score: 0

User: qwertyasdf

Problemset: รัฐบาล

Language: cpp

Time: 1.091 second

Submitted On: 2026-07-14 17:54:01

#include <bits/stdc++.h>

int count = 0;

void findmin(int x, int y, std::vector<std::vector<int>> graph, std::vector<int> &distant) {

    graph[x][y] = 0;
    graph[y][x] = 0;

    std::vector<bool> visited(graph.size(), false);
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    pq.push({0, 0});
    while(!pq.empty()) {
        if(visited[pq.top().second] == false) {
            int i = 0;
            int topnode = pq.top().second;
            distant[count] += pq.top().first;
            visited[pq.top().second] = true;
            pq.pop();
            for(int node : graph[topnode]) {
                if(node != 0 && visited[i] == false) {
                    pq.push({node, i});
                }
                i++;
            }
        }
        else {
            pq.pop();
        }
    }
    for(bool node : visited) {
        if(node == false) {
            distant[count] = 0;
            break;
        }
    }
    count++;
}

int main() {

    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> graph(n, std::vector<int>(n, 0));

    for(int i = 0; i < m; i++) {
        int c1, c2, l;
        std::cin >> c1 >> c2 >> l;
        graph[c1 - 1][c2 - 1] = l;
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(graph[i][j] != 0) {
                graph[j][i] = graph[i][j];
            }
        }
    }
// for(int i = 0; i < n; i++) {
//     for(int j = 0; j < n; j++) {
//         std::cout << graph[i][j] << " ";
//     }
//     std::cout << '\n';
// }

    std::vector<int> distant(m, 0);
    // std::vector<bool> visited(n, false);
    // std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    // pq.push({0, 0});
    // while(!pq.empty()) {
    //     if(visited[pq.top().second] == false) {
    //         int i = 0;
    //         for(int node : graph[pq.top().second]) {
    //             if(node != 0 && visited[i] == false) {
    //                 pq.push({node, i});
    //             }
    //             i++;
    //         }
    //         distant[0] += pq.top().first;
    //         visited[pq.top().second] = true;
    //         pq.pop();
    //     }
    //     else {
    //         pq.pop();
    //     }
    // }
    // std::cout << distant[0];
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(graph[i][j] != 0) {
                findmin(i, j, graph, distant);
            }
        }
    }

    std::sort(distant.begin(), distant.end(), std::greater<int>());
    for(int i = 0; i < m; i++) {
        if(distant[i] == 0) {
            while(i < m) {
                distant.pop_back();
                i++;
            }
        }
    }

    std::sort(distant.begin(), distant.end());
    std::cout << distant[0] << " " << distant[m - (n - 1)];

    return 0;
}