Download Speed

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

using namespace std;

// Function to find the maximum bandwidth path using a modified Dijkstra algorithm
int max_bandwidth(int n, const vector<vector<pair<int, int>>>& adj) {
    vector<int> max_bandwidth(n + 1, 0);  // Max bandwidth to reach each node
    priority_queue<pair<int, int>> pq;    // Max-heap (bandwidth, node)

    // Start from node 1 with infinite bandwidth
    max_bandwidth[1] = INT_MAX;
    pq.push({INT_MAX, 1});

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

        // If the current bandwidth is less than the best found so far, skip it
        if (bw < max_bandwidth[u]) continue;

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

            // Calculate the minimum bandwidth along this path
            int new_bw = min(bw, edge_bw);

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

    return max_bandwidth[n];  // Return the maximum 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
    }

    // Find and output the maximum bandwidth path from node 1 to node n
    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