DAG-dp DAG求单源最短距离
DAG求单源最短距离1.题目描述：上图所示的图为有向无环图(DAG)，现在需要求解从结点sss出发到达结点ttt的最短距离。2.基本思路由于该图为有向无环图因此其满足最优子结构的性质。定义函数f(i)f(i)f(i)，该函数表示从原点出发到达结点iii的最短距离。因此我们可以得到以下的递推关系式:f(T)=min{f(C)+20,f(D)+10}f(D)=min{f(B)+20,f(...
