zcmimi's blog

arrow_back最短路共15篇文章

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

点击跳转

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

点击跳转

n\le12

f[sta][x]表示状态为sta,当前位置为x的情况下最短的(字典序最小)

f[sta][y]=\min(f[sta'][x]+cost)

看到这个可以联想到AC自动机最短路(貌似是最短哈密顿路径?)

每个字符串长度都小于50,如果用AC自动机可能就核弹打蚊子

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

点击跳转

因为边权为1,所以直接跑奇偶最短路即可

但是当x=y时,我们需要判断x是否有向外连边

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

点击跳转

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

点击跳转

思路很妙

我们可以先求出n到每个点的距离

如果直接枚举k个干草堆,然后判断每个点是否可行,\Theta(nk)的复杂度显然TLE

因为一定要经过干草堆,所以可以新建一个节点n+1,向所有干草堆连单向边(边权为这个干草堆的影响)

在从n+1跑一遍最短路就可以了

2/2
Search
search