• 2024-09-0451nod 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