Question

ACM hust 1019 A dangerous trip

Answer 1

我表示你的水平越来越高了,得跟你相互探讨,看下这个哈：

对每个点保存两个值,做两遍最短路：

第一次普通最长路,

第二遍做最短路时,对所有边枚举其缩到一半的情况,具体就是：

Dist[p->v][1] = min(Dist[i][0]+p->len/2.0, Dist[i][1]+p->len)