週賽現在會錄影你寫的code
超屌
我原本一千多名
作弊抓完我就600名
笑死
題目:
在一個圖上面
找一個點
讓從node1 跟 2 走過去的其中一個距離最短
思路:
用兩次bfs找他們到每個點的距離
然後再遍歷每一個點假設他是那個點
這樣來找就可以了
```cpp
class Solution {
public:
int closestMeetingNode(vector<int>& edges, int node1, int node2)
{
int n = edges.size();
unordered_map<int,int> path;
for(int i = 0 ; i < n ; i ++)
{
path[i] = edges[i];
}
vector<int> paper1(n,-1);
vector<int> paper2(n,-1);
// now dist
queue<pair<int,int>> q;
q.push({node1,0});
paper1[node1] = 0;
while(!q.empty())
{
int now = q.front().first;
int dis = q.front().second;
q.pop();
if(path[now] != -1 && paper1[path[now]] == -1 )
{
q.push({path[now] , dis+1});
paper1[path[now]] = dis+1;
}
}
q.push({node2,0});
paper2[node2] = 0;
while(!q.empty())
{
int now = q.front().first;
int dis = q.front().second;
q.pop();
if(path[now] != -1 && paper2[path[now]] == -1 )
{
q.push({path[now] , dis+1});
paper2[path[now]] = dis+1;
}
}
int mi = INT_MAX;
int res = -1;
for(int i = 0 ; i < n ; i ++)
{
if (paper1[i] != -1 && paper2[i] != -1)
{
int ma = max(paper1[i], paper2[i]);
if(ma < minDist)
{
mi = ma;
res = i ;
}
}
}
return res;
}
};
```