LG 5122 [USACO18DEC]Fine-Dining

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转思路很妙我们可以先求出$n$到每个点的距离如果直接枚举$k$个干草堆,然后判断每个点是否可行,$\Theta(nk)$的复杂度显然 TLE 因为一定要经过干草堆,所以可以新建一个节点$n+1$,向所有干草堆连单向边(边权为这个干草堆的影响)在从$n+1$跑一遍最短路就可以了……