查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转仔细看题意,发现$k$最大只有$400$解法 1： 堆 贪心先把和每个点相连的所有边按边权从小到大排序。考虑一条路径的两个端点,如果这两个端点间的路径第一次被弹出（是两点间最短路）,则我们向其中一端扩展一条与它相连的最短边。现在假设堆顶有一条路径$u\rightarrow v$,它的一个端点$v$是由$u\rightarrow$扩展来的,此时我们可以尝试把与$x$相连的边中比$x\rightarrow v$权值略大的取出来（即排好序后的下一条边）,压到堆中。因为要处理两个端点比较麻烦,我们转化成有向……