NoipDay1T3逛公园

题目链接

NoipDay1T3逛公园

题解

不好好学\(dp\)和搜索

\(NOIp\)翻车怪谁

刚才报名北大冬令营,然后心态爆炸.


其实很简单.

我们不需要求出所有点之间的最短路.

只用一遍\(SPFA\)跑出第一个点到所有点的最短路.

其实就相当于创建了一个\(DAG\)图.

我们只需要在这个\(DAG\)上面想一下怎么\(dp\)就好了.

什么?为什么要\(dp\)?

你没有发现第一天的\(dp\)还没出现么.

题目中说明要求出\(1-N\)号中的长度不超过\(d+k\)的路线.

所以我们需要用动态规划的思想求出最优解.


至于环的问题.我们可以在记忆化搜索的遍历图的时候顺便再说~

我们在\(DAG\)上\(DP\),设\(dis[x]\)表示的是\(x\)节点的最短路.

\(f[x][k]\)表示到了\(x\)这个节点,距离比\(dis[x]\)大\(k\)的方案数.

状态转移.

\[f[x][k]=f[v][k+dis[x]-dis[v]-E[i].w]\]

边界

\(f[1][0]\)=1

最后统计一下答案就好了.

\[\sum_{i=1}^nf[n][i]\]


怎么解决这个环呢?

倒着\(dfs\),跳过距离差在\(k\)以内的特殊情况.

然后判环就好了.


By:Wahacer

2017.12.22

16:40

发表评论

电子邮件地址不会被公开。 必填项已用*标注