hdu 3873 Invade the Mars (有限制条件的最短路。。)

hdu3873题目链接

题意:n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。

思路:。。一开始写了spfa。。。然后一脸懵逼。。。因为我第一次访问某个点的时候无法保证距离是最短的。。。所以还是上dij吧。。。

然后dij写得比较少。。。不是很熟练。。参考了这篇题解参考题解

思路倒是不难想,我在写spfa的时候也是这样想法,然后试图记录路径递归来搞。。。。。然而并不可以2333

也是第一次遇到带限制条件的最短路。。。还是多积累吧。。。

哦对了。。。权值比较大。。。要记得开long long

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz