string的copy是O(n)的，换成
node &arr = q.front()试试？
by qcode_aya @ 2024-03-10 23:53:23
啊好像还有另一处…该换的都换了复杂度应该就正确了吧qwq
by qcode_aya @ 2024-03-10 23:54:45
不过不知道写引用会不会因为pop掉CE，实在不行记前驱叭
by qcode_aya @ 2024-03-10 23:56:16
@[qcode_aya](/user/1021745) 显然不能改引用吧，这里没道理可以引用的。记前驱是对的。
by N_z_ @ 2024-03-11 09:17:27
@[N_z_](/user/320087) 大晚上脑袋糊涂了…谢谢指正呢。本来想的是按楼主那样存状态怎么办的，不过楼主状态构造的复杂度问题，解决方案实际上与记前驱没区别（或许可以队列里存指针然后状态存前驱指针？但是这非常不美观）总之谢谢呢
by qcode_aya @ 2024-03-11 13:57:55
@[qcode_aya](/user/1021745) 什么是记前驱？怎么记前驱？
by stils @ 2024-03-13 22:19:22
@[stils](/user/1009027) 比如说状态A转移到B，就把B的前驱记为A，输出的时候从终点往前找前驱，然后倒序输出
by qcode_aya @ 2024-03-13 23:36:00
@[stils](/user/1009027) 对应到你代码里就是，状态是你结构体里存的字符串，转移的时候访问到了另一个节点，然后呢本来要copy当前状态的字符串并把下一个节点添加到末尾，这时改为把下一个节点的前驱标记为当前节点就好了。你会发现这样实际上每个节点状态是由起点到它的路径构成的，把链上的所有节点拼起来就是当前节点的状态。这样避免了每次需要copy当前字符串而作为新状态的前缀（转移出去k次就copy k次，而每次copy是O(n)的），保证了复杂度
by qcode_aya @ 2024-03-13 23:42:14