江三

题解

/ 注册

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

每日一题 wpy的请求 (spfa)

一.题意给出 n 个点和 m条边的有向图，边权可能为负值，修改任意边权，使所有边权非负且任意<u,v>的最短路路径不变。二.题解关键点在于两个：建图。最短路+负边权不难联想到，由于是单源最短路，所以要增加一个超级源点，保证原本的 n 个点都有对应的最短路。边权。最短路松弛...

每日一题 spfa

2020-07-23

0 744