Meul

题解

11eyes的算法笔记(4) ACM(1) Atcoder(14) BFS(1) codeforces(38) DFS(2) dp(3) ICPC(1) sublime text 3(1) 容斥(1) 未归档(10) 模拟(1) 洛谷(2) 牛客(26) 牛客题霸(1)

/ 注册

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

NC204867 旅旅旅游

Question 牛妹在城市 1，他想把所有城市走一遍，可是她不想走可以属于从1到n的最短路的路径，牛妹不知道他能不能将所有城市全走一遍，你能告诉她吗？ Solution djikstra 并查集 djikstra两遍求从1到n的最短路和从n到1的最短路。判断每一条路是否为最短路，若非最短路则将...

最短路 djikstra 并查集

2020-04-20

2 524

NC5026D

题意一张连通有向图，另一条边反向，是否缩短了1到n的最短路？保证开始给定的图从城市1可以到达城市n，若边反向后城市1不能到达城市n，我们视为最短路径长度没有变短。思路数据范围较大，最原始的暴力每次djikstra一遍肯定是TLE的，于是思考预处理，预先djiksra一遍。每次反向一条边和没反向...

最短路 djikstra

2020-04-11

3 559