LeetCode 5355. T 秒后青蛙的位置

798236606

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

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

1. class Solution {
   
2. public:
   
3.     vector<int> adj[105];
   
4.     double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
   
5.         for (auto edge: edges) adj[min(edge[0], edge[1])].push_back(max(edge[0], edge[1]));
   
6.         
   
7.         queue<pair<int, double>> q;
   
8.         q.push({1, 1.0});
   
9.         
   
10.         while (int k = q.size())
    
11.         {
    
12.             while (k--)
    
13.             {
    
14.                 auto now = q.front();
    
15.                 q.pop();
    
16.                
    
17.                 int num = adj[now.first].size();
    
18.                 if (target == now.first) return (!t || (t > 0 && !num)) ? now.second : 0.0;
    
19.                 for (int each: adj[now.first]) q.push({each, now.second / num});               
    
20.             }
    
21.             --t;
    
22.         }
    
23.         
    
24.         return 0.0;
    
25.     }
    
26. };

复制代码