求此题题解

学术版

ddlove2014 @ 2024-11-29 15:52:02

玩家在和他的好朋友玩你追我跑的游戏 若玩家主动碰到好朋友就会输掉比赛, 好朋友下一秒会来到上一秒玩家的位置，玩家早于好朋友移动，这轮时间一共

$k$秒时间到则玩家胜利 这间屋子有 $n$个点可以走 ，有 $m$条通道（均为单向) 现在小L想知道玩家从 $t$点开始能否撑过 $k$秒 模拟下： 1 -> 2 -> 3 从1点开始， 第1秒：玩家：1 好朋友：未出现 第2秒：玩家：2 好朋友：1 第3秒：玩家：3 好朋友：2 第4秒开始，玩家无路可逃，只能被好朋友抓住了 所以从1点开始可最多一轮3秒时间，玩家就会被抓住了。 保证无重边，自环 可能有环.可能有环.可能有环.可能有环.可能有环.可能有环.可能有环.可能有环.可能有环.可能有环! 站外题，不会做，大佬们给个思路

by bsdsdb @ 2024-11-29 16:02:13

@ddlove2014 上午看到有人问过？我还回答了？

by bsdsdb @ 2024-11-29 16:02:56

先判环，有环长度大于2并且能走到就无敌了，否则就是DAG上dp

by bsdsdb @ 2024-11-29 16:04:15

可以缩点，但是怎么判断能不能走到环

|