网站首页
编程语言
数据库
系统相关
其他分享
编程问答
城际
2024-09-04
51nod 2842 城际旅行
原题链接这题因为要求满足t时间内,所以用dp,不过我们的状态比较特殊,\(dp[i][j]\)表示到\(i\)点时经过\(j\)个点的最短时间,因为题目为DAG所以要用拓扑排序,每到一个点,枚举所有出边,更新出点的状态\(f[v][j+1]=min(f[v][j+1],f[u][j])\),最后的答案就是所有\(f[t][j]\let