首页 > [HAOI2012]ROAD
开通博客写题解
头像 sunrise__sunrise
发表于 2021-03-19 21:55:53
Solution 首先看数据范围比较有限，所以我们要计算每条路被做为最短路通过的次数，那么我们就可以分各个点进行处理。我们每次都枚举一个源点做为最短路的起点，求解最短路的话使用这样我们就可以求解出去各个点的最短长度，接下来我们就考虑一个最短路图的概念，我们通过求解得到的数组很显然如果是第一次显然这条 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 jzdx（hjh）
发表于 2021-03-28 10:01:50
题号 NC19987名称 [HAOI2012]ROAD来源 [HAOI2012] 题目描述 C国有n座城市，城市之间通过m条单向道路连接。一条路径被称为最短路，当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估 展开全文
去ta的博客 赞 (2) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”