Untitled

unknown
plain_text
12 days ago
3.0 kB
4
Indexable
Never
```class Solution {
public:
int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
vector<vector<pair<int, int>>> G;
G.assign(n + 1, {});
for (vector<int> &e : edges) {
G[e[0]].emplace_back(e[1], time);
G[e[1]].emplace_back(e[0], time);
}
vector<int> visited(G.size(), -1);
auto [SPN, minimum] = BFS(visited, G, n, time, change);
int secondMinimum;
if (sameLevel(visited, G, SPN)) {
secondMinimum = minimum + isRedLight(minimum, change) + time;
}
else secondMinimum = minimum + isRedLight(minimum, change) + time + isRedLight(minimum + isRedLight(minimum, change) + time, change) + time;
return secondMinimum;
}

pair<unordered_map<int, bool>, int> BFS(vector<int> &visited, vector<vector<pair<int, int>>> &G, int t, int time, int change) {
using QueuePair = tuple<int, int, int>; // cost, level, node
priority_queue<QueuePair, vector<QueuePair>, greater<QueuePair>> Q;
Q.emplace(make_tuple(0, 0, 1));
int minimum = INT_MAX;
while (!Q.empty()) {
auto [costU, levelU, u] = Q.top();
Q.pop();
if (visited[u]!=-1) continue;
visited[u] = levelU;
for (auto &[v, cost] : G[u]) {
int trafficLightCost = isRedLight(costU + cost, change);
int costV = costU + cost;
if (v == t && minimum == INT_MAX) minimum = costV;
Q.emplace(costV + trafficLightCost, levelU + 1, v);
}
}
unordered_map<int, bool> SPN;
Q.emplace(make_tuple(-1, 0, t));
SPN[t] = true;
while (!Q.empty()) {
auto [costU, levelU, u] = Q.top();
Q.pop();
for (auto &[v, cost] : G[u]) {
if (visited[v] == visited[u] - 1) {
SPN[v] = true;
Q.emplace(-1, levelU + 1, v);
}
}
}
// for (auto v : SPN) {
//     cout << v << " ";
// }
return pair{SPN, minimum};
}
int isRedLight(int time, int change) {
// 0 ~ change - 1 -> green
// change ~ 2 * change - 1 -> red
// 2 * change ~ 3 * change - 1 -> green
// 3 * change ~ 4 * change - 1 -> red
// 4 ~ 7, 12 ~ 15, 20 ~ 23
// change <= % 2 * change <= 2 & change - 1
if (change <= time % (2 * change) && time % (2 * change) <= 2 * change - 1) {
return 2 * change - time % (2 * change);
}
return 0;
}
bool sameLevel(vector<int> &visited, vector<vector<pair<int, int>>> &G, unordered_map<int, bool> &SPN) {
for (auto &node : SPN) {
int u = node.first;
for (auto &[v, cost] : G[u]) {
if (visited[v] == visited[u])
return true;
}
}
return false;
}
};```