Re: [閒聊] 每日LeetCode
1129. Shortest Path with Alternating Colors
給 n 個點，紅色的有向邊，藍色的有向邊，可能包含自環或是重邊(顏色不同)，
求從 0 號點出發，用交錯邊到每個點的最短路徑，若無法到達則是-1。
Example 1:
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]
Explanation: 從 0 號點只能從紅邊到 1 號點，沒有藍邊可以繼續前往 2 號點
Example 2:
Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]
Explanation: 從 0 號點到 1 號點後，藍邊[2, 1]是有向邊，無法從 1 號到 2 號
解題思路：
對於每個點紀錄由紅邊到達以及藍邊到達的最短路徑，
把存邊的資料結構改成 adjacency lists 會比較容易存取，
從 0 號點開始進行 BFS，出發的邊可以是紅邊也可以是藍邊，
如果是用紅邊到達的點就用藍邊來更新鄰居，藍邊就反過來，
每個點最多只會被更新 2 次。
C++ code:
#define RED 0
#define BLUE 1
class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>&
redEdges, vector<vector<int>>& blueEdges) {
vector<vector<int>> dis(n, {INT_MAX, INT_MAX});
vector<vector<int>> red(n, vector<int>()), blue(n, vector<int>());
for(auto i : redEdges)
red[i[0]].push_back(i[1]);
for(auto i : blueEdges)
blue[i[0]].push_back(i[1]);
dis[0] = {0, 0};
queue<pair<int, int>> que; // {node, color}
que.push({0, RED});
que.push({0, BLUE});
while(que.size() > 0){
auto [id, color] = que.front(); que.pop();
if(color == RED){
for(auto i : blue[id]){
if(dis[id][RED] + 1 < dis[i][BLUE]){
dis[i][BLUE] = dis[id][RED] + 1;
que.push({i, BLUE});
}
}
}
else{
for(auto i : red[id]){
if(dis[id][BLUE] + 1 < dis[i][RED]){
dis[i][RED] = dis[id][BLUE] + 1;
que.push({i, RED});
}
}
}
}
vector<int> ans(n);
for(int i = 0; i < n; i++){
ans[i] = min(dis[i][RED], dis[i][BLUE]);
if(ans[i] == INT_MAX) ans[i] = -1;
}
return ans;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676075791.A.598.html
※ 編輯: idiont (140.113.229.216 臺灣), 02/11/2023 08:38:16
推
02/11 08:45,
2年前
, 1F
02/11 08:45, 1F
※ 編輯: idiont (140.113.229.216 臺灣), 02/11/2023 09:02:06
推
02/11 10:35,
2年前
, 2F
02/11 10:35, 2F
討論串 (同標題文章)
完整討論串 (本文為第 228 之 719 篇)：