娱乐 每 日 算 法 挑 战 （大嘘）【第0x16期】

[yhz012]

反正先跑一遍1的算法不亏，同样的道理，如果最短路径d < s,或者d - s是奇数，就可以直接放弃治疗了

对于d-s是偶数的情况那就需要额外判断是否存在指定长度的迂回路径了……

感觉可以考虑用类似iterative dfs的想法解？就是限制dfs深度在s上，如果求到了K-S路径，那就能跑，求不到就凉了

不对，似乎有问题，除非同时维护多个closed list，否则idfs也一样会出现incomplete的问题

 

所以还是考虑迂回路径似乎更靠谱一点

如果迂回路径存在，那首先这个图要存在环，所以不存在环的情况可以直接打死了

（总觉得这回问题比我想的要难了……我甚至怀疑是NP级别的

自信点，把觉得删了。我可以不断增加s大小，这样这个问题可以用来找到一个图里的最长简单路径。已知最长简单路径是NPC，这问题没跑了

五月 7, 2020，由yhz012修改

[yhz012]

1 小时前, PhoeniXLL 说道:

快请布鲁特·福斯先生过来

艹我想了半天这是谁，然后我想起来了brute force

 

↓我真的以为有现成的算法来判定无向图中2顶点间是否存在给定长度路径的算法，然后百度搜到是字符串匹配算法，就很迷惑

五月 7, 2020，由yhz012修改

[yhz012]

13 小时前, Mr.K 018 说道:

这个题数据量没那么大，我记得正解就是布鲁特·福斯算法（

噗，那最坏情况就给每个路径单独维护一个closed list，然后dfs限定最大深度s跑起来就完了（