Re: [閒聊] 每日leetcode
週賽現在會錄影你寫的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;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.1.248 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1748592137.A.BEE.html
推
05/30 16:03,
6月前
, 1F
05/30 16:03, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1439 之 1548 篇)：