UVa-10917 Walk Through the Forest [最短路+DP/记忆化递归]

题目:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1858

uva访问不到的可以去vjudge上:https://vjudge.net/problem/UVA-10917

题目大意是说有两个点1,2. 从1出发走到2,每次只走可以make progress的路径, 所谓的make progress的A到B的边指的是从存在B到2的某条路比A到2的任何路的长度都要小,实际上就是B到2的最短路比A到2的最短路要短。可以用单源最短路求出2出发的所有最短路,然后从1开始做一个DFS就可以求出正确答案。但是需要注意的就是这个DFS要记忆化一下,否则会TLE

继续阅读“UVa-10917 Walk Through the Forest [最短路+DP/记忆化递归]”