LeetCode 5355. T 秒后青蛙的位置

798236606

传送门：https://leetcode-cn.com/problems/frog-position-after-t-seconds/

解：
建图+BFS（DFS也可）
t其实是对层数的限制，用BFS比较好理解。
注意青蛙在目的地停留的条件：
1.所在层数（顶点层数按0算）等于t
或
2.所在层数小于t，但目的地为叶节点

class Solution {
public:
    vector<int> adj[105];
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        for (auto edge: edges) adj[min(edge[0], edge[1])].push_back(max(edge[0], edge[1]));
        
        queue<pair<int, double>> q;
        q.push({1, 1.0});
        
        while (int k = q.size())
        {
            while (k--)
            {
                auto now = q.front();
                q.pop();
                
                int num = adj[now.first].size();
                if (target == now.first) return (!t || (t > 0 && !num)) ? now.second : 0.0;
                for (int each: adj[now.first]) q.push({each, now.second / num});                
            }
            --t;
        }
        
        return 0.0;
    }
};