CSES - Aalto Competitive Programming 2024 - wk7 Homework - Results
Submission details
Task:Download Speed
Sender:louaha1
Submission time:2024-10-24 09:32:00 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#20.00 sdetails
#30.00 sdetails
#40.00 sdetails
#50.00 sdetails
#60.00 sdetails
#70.01 sdetails
#8ACCEPTED0.00 sdetails
#90.00 sdetails
#100.00 sdetails
#110.00 sdetails
#120.00 sdetails

Code

#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 details

Test 1

Verdict: ACCEPTED

input
4 3
1 2 5
2 3 3
3 4 6

correct output
3

user output
3

Test 2

Verdict:

input
4 5
1 2 1
1 3 1
2 3 1
2 4 1
...

correct output
2

user output
1

Test 3

Verdict:

input
4 5
1 2 1000000000
1 3 1000000000
2 3 1
2 4 1000000000
...

correct output
2000000000

user output
1000000000

Test 4

Verdict:

input
2 1
2 1 100

correct output
0

user output
100

Test 5

Verdict:

input
2 1000
1 2 1000000000
1 2 1000000000
1 2 1000000000
1 2 1000000000
...

correct output
1000000000000

user output
1000000000

Test 6

Verdict:

input
500 998
1 2 54
1 3 59
1 4 83
2 5 79
...

correct output
60

user output
54

Test 7

Verdict:

input
500 998
1 2 530873053
1 3 156306296
1 4 478040476
3 5 303609600
...

correct output
1093765123

user output
688173231

Test 8

Verdict: ACCEPTED

input
2 1
1 2 1

correct output
1

user output
1

Test 9

Verdict:

input
4 5
1 2 3
2 4 2
1 3 4
3 4 5
...

correct output
6

user output
4

Test 10

Verdict:

input
4 5
1 2 1
1 3 2
3 2 1
2 4 2
...

correct output
3

user output
1

Test 11

Verdict:

input
10 999
1 2 1000000000
1 2 1000000000
1 2 1000000000
1 2 1000000000
...

correct output
111000000000

user output
1000000000

Test 12

Verdict:

input
7 9
1 2 1
1 3 1
1 4 1
2 5 1
...

correct output
2

user output
1