zcmimi's blog

arrow_backfloyed共2篇文章

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

仔细看题意,发现k最大只有400

解法1: 堆 贪心

先把和每个点相连的所有边按边权从小到大排序。

考虑一条路径的两个端点,如果这两个端点间的路径第一次被弹出(是两点间最短路),则我们向其中一端扩展一条与它相连的最短边。

现在假设堆顶有一条路径u\rightarrow v,它的一个端点v是由u\rightarrow扩展来的,此时我们可以尝试把与x相连的边中比x\rightarrow v权值略大的取出来(即排好序后的下一条边),压到堆中。

因为要处理两个端点比较麻烦,我们转化成有向路径(只有一个端点),然后取第2k大的。

记住我们需要维护的信息:路径的两个端点st,ed,端点ed前面的点x(即ed是由st\rightarrow x扩展来的),以及这条路径的长度。

解法2: floyd

考虑答案应该小于等于第k小的边的长度。因此只有前k小的边对答案有贡献。这k条边构成的子图的节点数也是O(k)的,于是我们就可以做floyd了。

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

点击跳转

题解很妙

f[i][j][k]为从ijk步的方案数

f[i][j]这个矩阵的k次方就是答案

ans = \sum f[1][i]

1/1
Search
search