本文共 2611 字，大约阅读时间需要 8 分钟。

潜入苏拉玛

时间限制: 1 Sec 内存限制: 128 MB

题目描述

你接到了⼀个任务，让你潜⼊苏拉玛城，和线⼈取得联络。苏拉玛的地图是⼀张N个点M条边的⽆向图，每个点表⽰苏拉玛城的⼀个路⼜，每条边表⽰苏拉玛内的⼀条道路，长度都是1。你从S号节点出发，线⼈在T号节点。 由于苏拉玛城内都是夜之⼦的哨兵，你需要假⾯伪装才能在苏拉玛的道路上⾏⾛。你的伪装只能坚持你⾛完K段道路不被发现，幸好在苏拉玛城内还有P个内应（分别在节点ai上），他们可以修复你的伪装，让它恢复到刚开始的状态。 你想知道K⾄少需要是多少，才能让你成功找到线⼈。 输入 第⼀⾏⼀个正整数CAS表⽰测试数据组数。 每组测试数据第⼀⾏有三个数N,M,P如上⽂所述，第⼆⾏P个数表⽰内应的位置。接下来M⾏，每⾏2个数表⽰⼀条边。最后⼀⾏S和T表⽰你开始的节点和你的⽬标节点。 输出 对于每组数据：如果你⽆法到达线⼈那⾥，输出-1，否则输出最⼩的K。 样例输入 Copy 2 6 6 3 1 3 6 1 2 2 3 4 2 5 6 4 5 3 4 1 6 7 10 3 1 3 4 1 2 4 2 7 5 4 5 7 1 2 5 7 2 3 7 3 2 5 1 4 6 样例输出 Copy 3 -1 提示 对于100%的数据，1≤K,S,T≤N≤100000,1≤M≤150000,1≤CAS≤5。

刚从大佬那里嫖来的思路，感觉挺有意思的。

题意就是给你几个内应的位置，每次走过的路径段数不超过 k 条，内应可以补满剩余可走的路径段，让后求 k 的最小值。 思路无非就是当不能走到终点的时候，一定需要一个内应来做媒介，补充步数。几种情况无非就是 从起点到内应点，从内应点到内应点，等等，也就是说我们需要保证对于每个不能直接走到终点的点，一定需要一个内应点，到这个内应点的距离 <= k。 我们可以把 内应位置、起点、终点 放入队列中，做一个多端bfs，那么当两个点相会的时候，即为这两个点的中点处，假设当前 bfs 的总体层数为 ans 那么 k 就为 ans * 2 。显然前面那个是不对的，当两个点之间是奇数呢？假设当前就俩点，一个起点，一个终点，他俩之间有两个点连接，也就是三条边，那么应该是在第二次扩展的时候两点相会，这时候退出答案为4，但是答案应该是3 。如果知道当前两点之间的数为奇数还好说，直接减一，但是如何不需要知道两点之间的数是否为奇数就可以做呢？考虑到我们最终需要乘 2 ，那么可以通过加边来完美解决这个问题，也就是说，如果当前需要加 u 和 v ，那么把 u 和 n + i 连接，n + i 和 v 连接，也就是把原来 a - b 改成 a - c - b ，通过一个媒介，将路径长度都变成偶数，可以再模拟下上面的样例，答案为3。 还有个问题，怎么判断当前两个点是否连通呢？相比上面，这个就比较容易想到了，用并查集来判断连通。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/106058173 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！