-
Notifications
You must be signed in to change notification settings - Fork 1.6k
/
minimum-score-of-a-path-between-two-cities.cpp
42 lines (40 loc) · 1.2 KB
/
minimum-score-of-a-path-between-two-cities.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Time: O(n + m), m = len(roads)
// Space: O(n + m)
// bfs
class Solution {
public:
int minScore(int n, vector<vector<int>>& roads) {
vector<vector<pair<int, int>>> adj(n);
for (const auto& r : roads) {
adj[r[0] - 1].emplace_back(r[1] - 1, r[2]);
adj[r[1] - 1].emplace_back(r[0] - 1, r[2]);
}
const auto& bfs = [&]() {
vector<bool> lookup(size(adj));
vector<int> q = {0};
lookup[0] = true;
while (!empty(q)) {
vector<int> new_q;
for (const auto& u : q) {
for (const auto& [v, w] : adj[u]) {
if (lookup[v]) {
continue;
}
lookup[v] = true;
new_q.emplace_back(v);
}
}
q = move(new_q);
}
return lookup;
};
const auto& lookup = bfs();
int result = numeric_limits<int>::max();
for (const auto& r : roads) {
if (lookup[r[0] - 1]) {
result = min(result, r[2]);
}
}
return result;
}
};