CF1842D
原题
翻译
题目背景生草
因为我们想让聚会时间越长越好，所以我们对于从1开始的某一个限制，我们直到他到达了最大时间再把他加入，由此得到答案的上限为\(1 \rightarrow n\)的最短路，且这个上限是总是可以取到的
因此如果这个上限\(> 10^{18}\)就可以结束了
否则我们考虑以下构建集合的方法：
- 集合中始终有1
- 按照\(1 \rightarrow i\)的最短路从小到大排序，每个点依次加入，这样可以得到加点顺序
- 当前这个集合的方案持续时间为当前加入点的距离-上一个加入点的距离
使用dij的话复杂度\(O(mlogm+nlogn)\)，题解用了flody\(O(n^3+nlogn)\)
ps:有中文题解好耶