NOIp2017 Day1T3 逛公园(SPFA+记忆化DP)

Description

Solution

对于30%的数据,显然可以SPFA后暴力DFS

对于100%的数据

SPFA+记忆化DP

时间复杂度
如果没有零环,从终点倒序记忆化DP即可

考虑在最短路+k内的零环:如当前DFS中,符合条件(vis[e[i].too][k])的点被再次遍历return -1即可

 

3.5 2 votes
Article Rating
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments