hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

全部文章 / 题解（共1篇）

wpy的请求

题意：给你一个n个结点m条边的有负权边无负环的有向图，为每条边赋一个非负新值，在新图上的u到v的最短路上的点和原图上最短路上的点相同且顺序不变。思路：参考了多篇题解，我们造一个超级源点与每一个点相连，且边权为0，从超级源点开始跑spfa;我们这m条边的新值为d[u]-d[v]+cost(u,v);...

spfa

2020-07-30

0 604