推 mrsonic: 寫爽沒 07/28 17:16
→ oin1104: 管好你自己 07/28 17:16
推 sustainer123: 大師 07/28 17:23
→ SydLrio: 你有什麼用 07/28 17:37
推 JIWP: 我好崇拜你 07/28 17:48
→ DJYOMIYAHINA: 法國我 07/28 17:55
題目:
有點難理解
給你一張圖
有n個節點 還有一堆路徑
每個路徑要走的時間都是time
每隔change秒
紅綠燈會變號
紅燈的時候你不能出發
但是已經在走的人可以抵達
請問第二短到達第n個節點的時間是什麼
思路:
想很久
然後跑去看提示
知道可以直接用bfs來找每個節點
然後因為每個路徑都花一樣時間
所以所以可以用queue塞
反正同節點後面出現的一定比較大
因為 就
bfs
對ㄚ
然後要全部記起來
找第二大的
怎麼找
細節還是不知道怎麼做
偷看一下
用陣列第i格紀錄
一定要強制比較小
才可以放進去
然後同時增加visited
超過兩次visited 是不可以的
然後同時還有處理紅燈的問題
就是看當時是什麼燈
紅燈 -> 加到紅燈結束
綠燈 -> 屁眼
這題有點複雜
還有一堆小雞巴細節
建議不懂的去看yt比較快
有沒有可愛的女孩子可以跟我交往
```cpp
class Solution {
public:
int secondMinimum(int n, vector<vector<int>>& edges, int time, int change)
{
int len = edges.size();
unordered_map<int,vector<int>> save;
for(int i = 0 ; i < len ; i ++)
{
save[edges[i][0]].push_back(edges[i][1]);
save[edges[i][1]].push_back(edges[i][0]);
}
queue<pair<int,int>> paper;
vector<int> visited(n+1,0);
vector<int> all (n+1,-1);
all[1]=-1;
paper.push({1,0});
int curtime = 0;
while(!paper.empty())
{
pair<int,int> now = paper.front();
paper.pop();
if((now.second%(change*2)) >= change)
{
now.second = now.second + (change*2) - (now.second%(change*2));
}
for(int k : save[now.first])
{
if(visited[k] <2 && all[k]<now.second+time)
{
all[k]=now.second+time;
visited[k]++;
paper.push({k,now.second+time});
}
}
}
return all[n];
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.47.70 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722158012.A.743.html