aboutsummaryrefslogtreecommitdiff
path: root/shortest_path_alternate_color.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'shortest_path_alternate_color.cpp')
-rw-r--r--shortest_path_alternate_color.cpp56
1 files changed, 0 insertions, 56 deletions
diff --git a/shortest_path_alternate_color.cpp b/shortest_path_alternate_color.cpp
deleted file mode 100644
index a5cf369..0000000
--- a/shortest_path_alternate_color.cpp
+++ /dev/null
@@ -1,56 +0,0 @@
-// 1129. Shortest Path with Alternating Colors
-#include "leetcode.h"
-
-class Solution {
-public:
- vector<int> shortestAlternatingPaths(int n, vvd & redEdges,
- vvd & blueEdges) {
- vector<int> ans(n, -1), v1(n, 0), v2(n, 0);
- vector<vector<pair<int, int>>> vvp(n);
- queue<pair<int, int>> qp;
- for (auto &it : redEdges)
- vvp[it[0]].push_back({it[1], 1});
- for (auto &it : blueEdges)
- vvp[it[0]].push_back({it[1], 2});
- ans[0] = 0, v1[0] = 1, v2[0] = 1;
- int tmp = 1;
- for (auto &it : vvp[0]) {
- qp.push(it);
- if (ans[it.first] == -1)
- ans[it.first] = tmp;
- }
- while (!qp.empty()) {
- int len = qp.size();
- tmp++;
- for (int i = 0; i < len; ++i) {
- auto val = qp.front();
- qp.pop();
- if (val.second == 1)
- v1[val.first] = 1;
- else
- v2[val.first] = 1;
- for (auto &it : vvp[val.first]) {
- if (val.second == 1 && (v2[it.first] || it.second == 1))
- continue;
- if (val.second == 2 && (v1[it.first] || it.second == 2))
- continue;
- qp.push(it);
- if (ans[it.first] == -1)
- ans[it.first] = tmp;
- }
- }
- }
- return ans;
- }
-};
-
-int main() {
- Solution obj;
- vvd re1 = {{0, 1}, {1, 2}}, be1 = {};
- vvd re2 = {{0, 1}}, be2 = {{2, 1}};
- for (auto i : obj.shortestAlternatingPaths(3, re1, be1))
- cout << i << ' '; // expect: 0 1 -1
- cout << endl;
- for (auto i : obj.shortestAlternatingPaths(3, re2, be2))
- cout << i << ' '; // expect: 0 1 -1
-}