zcmimi's blog

arrow_backspfa共2篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

玄学的最短路优化

一看数据范围这么大,一定不能直接做

当你删掉某条边(u,u+1)时,最短路路线为:1->x(<=u)->y(>u)->n,并且x->y一定不会属于原最短路

就是最短路->其他边->最短路

ban:(禁用)

先把所有堵车的边ban掉,然后跑最短路

接着依次加边,跑最短路,就不用清空dis了

d(x,y)xy的最短距离

每个点的答案就是d(1,x)+d(x,n)

所以开一个堆,

枚举被ban的边

把答案和没被ban的边的编号扔进去就可以了

avatar
zcmimi
2019-01-21 18:36:18

LG 3953 逛公园

题意: 求dis(1,n)<=MinDis(1,n)+K的路径数

用拓扑啊什么的一想就很麻烦。

有一种玄学的做法:记忆化搜索

f[x][k]表示dis(x,n)<=MinDis(x,n)+k的路径数。

先跑一般反向的最短路,然后dfs

考虑边(x,y,w),

\because Mindis[x]-Mindis[y]+w<k

\therefore f[x][k]+=f[y][k-(Mindis[x]-Mindis[y]+w)]

\therefore f[x][k] = \sum f[y][k-(Mindis[x]-Mindis[y]+w)]

1/1
Search
search