class Solution {
public:
int RED = 0;
int BLUE = 1;
vector<vector<pair<int, int>>> graph;
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
graph.clear();
graph.resize(n);
for(auto& v: redEdges) {
graph[v[0]].emplace_back(RED, v[1]);
}
for(auto& v: blueEdges) {
graph[v[0]].emplace_back(BLUE, v[1]);
}
// color, current node
queue<pair<int,int>> q;
vector<vector<int>> distance(2, vector<int>(n, 1e9));
distance[BLUE][0] = distance[RED][0] = 0;
q.push({RED, 0});
q.push({BLUE, 0});
while(!q.empty()) {
auto [color, idx] = q.front();
q.pop();
int dist = distance[color][idx];
for(int i = 0 ; i < graph[idx].size(); i++) {
auto [ncolor, nidx] = graph[idx][i];
if(ncolor != color && distance[ncolor][nidx] == 1e9) {
distance[ncolor][nidx] = dist + 1;
q.push({ncolor, nidx});
}
}
}
vector<int> ret = distance[RED];
for(int i = 0; i < n; i++) {
ret[i] = min(ret[i], distance[BLUE][i]);
if(ret[i] == 1e9) {
ret[i] = -1;
}
}
return ret;
}
};
자고 일어나서 품..
댓글 영역
획득법
① NFT 발행
작성한 게시물을 NFT로 발행하면 일주일 동안 사용할 수 있습니다. (최초 1회)
② NFT 구매
다른 이용자의 NFT를 구매하면 한 달 동안 사용할 수 있습니다. (구매 시마다 갱신)
사용법
디시콘에서지갑연결시 바로 사용 가능합니다.