2/3 熬夜刷题~~~

https://www.luogu.com.cn/problem/P3906 P3906 Geodetic集合 bfs深搜的灵活应用，算我的薄弱点。

#include 

using namespace std;
const int inf=0x3f3f3f3f;
int n,m,pre[50][50],dist[50],mp[50][50],k,num[50];
bool vis[50];
void bfs(int s,int t)
{
    memset(num,0,sizeof(num));     //记录前驱结点个数
    memset(dist,inf,sizeof(dist)); //dist数组都初始化为极大值，吴话可说
    dist[s]=0;                     //起始结点距离为0
    queueq;q.push(s);
    while(!q.empty())
    {
        s=q.front();q.pop();
        for(int i=1;idist[s]+1)  //简单dp思想
                {
                    dist[i]=dist[s]+1;
                    pre[i][++num[i]]=s;  //以i为节点的前驱节点都标记为s（上一个结点），num[i]表示几个
                    q.push(i);
                }
                else if(dist[i]==dist[s]+1)
                    pre[i][++num[i]]=s;
            }
        }
    }
    memset(vis,0,sizeof(vis));q.push(t);vis[t]=1; //从目标结点t倒着搜上去
    while(!q.empty())
    {
        s=q.front();q.pop();
        for(int i=num[s];i>=1;i--)  //以s为结点的前驱节点，标记为1
        {
            if(!vis[pre[s][i]])
                vis[pre[s][i]]=1;
                q.push(pre[s][i]);
        }
    }
    for(int i=1;i