Download Speed

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
const int MAXN = 505;
vector<pair<int, int>> adj[MAXN];  // adjacency list: (neighbor, bandwidth)
bool visited[MAXN];
int max_bandwidth[MAXN];  // max bandwidth to reach each node
 
int dijkstra(int n) {
    priority_queue<pair<int, int>> pq;  // (bandwidth, node)
    memset(visited, false, sizeof(visited));
    memset(max_bandwidth, 0, sizeof(max_bandwidth));
 
    max_bandwidth[1] = 1e9;  // start with an infinite bandwidth at the source
    pq.push({max_bandwidth[1], 1});  // Push source with infinite bandwidth
 
    while (!pq.empty()) {
        int bw = pq.top().first;
        int u = pq.top().second;
        pq.pop();
 
        if (visited[u]) continue;
        visited[u] = true;
 
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int edge_bw = edge.second;
 
            // Maximize the minimum bandwidth along the path
            int new_bw = min(bw, edge_bw);
            if (new_bw > max_bandwidth[v]) {
                max_bandwidth[v] = new_bw;
                pq.push({new_bw, v});
            }
        }
    }
    return max_bandwidth[n];  // return the max bandwidth to Kotivalo's computer
}
 
int main() {
    int n, m;
    cin >> n >> m;
 
    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, we can go both ways
    }
 
    int result = dijkstra(n);
    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