Download Speed

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

// Maximize the minimum bandwidth from node 1 to node n
int max_bandwidth(int n, const vector<vector<pair<int, int>>>& adj) {
    vector<int> bandwidth(n + 1, 0);  // max bandwidth to each node
    priority_queue<pair<int, int>> pq;  // (bandwidth, node)

    bandwidth[1] = INT_MAX;  // Start with infinite bandwidth at node 1 (the server)
    pq.push({INT_MAX, 1});   // Push node 1 with infinite bandwidth

    while (!pq.empty()) {
        int bw = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (bw < bandwidth[u]) continue;  // Already found a better path

        // Traverse neighbors
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int edge_bw = edge.second;

            // Compute the maximum minimum bandwidth for this neighbor
            int new_bw = min(bw, edge_bw);

            // If we find a better bandwidth for node v, update and push it to the priority queue
            if (new_bw > bandwidth[v]) {
                bandwidth[v] = new_bw;
                pq.push({new_bw, v});
            }
        }
    }

    return bandwidth[n];  // Return the max bandwidth to node n
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> adj(n + 1);  // Adjacency list

    // Read all connections
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});  // Undirected graph
    }

    int result = max_bandwidth(n, adj);
    cout << result << endl;

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: ACCEPTED

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER