题目大意

蝌蚪妈妈从家出发，蝌蚪根据一定的路线走，每秒妈妈移动一个位置，蝌蚪移动到确定的位置（路线走完，原地等待）。问妈妈最短需要多长时间找到蝌蚪。

分析与思路

题型

bfs，标签说明了，可以通过求最短时间判断。（因为我自己也不是很会判断，所以无法告诉大家判断方法）

转化

难点在于转化。（我没想到……）
我一直觉得很多题都是难在转化，当然，代码的实现也是难点，不过转化是基础。
分两种情况：
1.在不超过k秒内就能找到蝌蚪
2.在k秒之后才能找到蝌蚪
情况1分析：
不超过k秒就能找到。也就是说，如果妈妈可以在小蝌蚪到达某点之前（或一起）到达此点，那么就满足情况1。题目要求最短时间，那么我们就从1s~ks（从前往后）去遍历，只要小蝌蚪第i秒的位置，妈妈能提前（或一起）到达此位置，那么就是正确答案，这时候的时间一定是最短的。
情况2分析：

k秒之后才能找到。k秒以后，小蝌蚪就不动了，停在k秒时的位置。反正妈妈已经不可能在k秒内找到了，就不用动脑子去判断每一秒小蝌蚪的动态变化了，直接走最短的路径，直奔小蝌蚪停留的位置就行，此时的用时就是妈妈到达k秒小蝌蚪所在位置的最短时间。如何判断情况2是否满足？情况1的满足条件已经有了，就是可以判断情况1是否满足了，那么不是情况1就是情况2嘛。

思想

思想这个东西，我感觉是最难理解的，也是变化最多的。
对于本题而言，我只能片面的理解为“两个过程独立思考”。
我们不去同时进行小蝌蚪的行动和蝌蚪妈妈的行动，而是独立的求出妈妈的动向，再根据现实意义分情况讨论并联系在一起。
具体到本题，先bfs，确定所有位置妈妈到达的最短时间；判断属于哪种情况；按情况输出。

提醒

看懂题解与落实代码是完全两个概念，希望大家能动起手来。
详细的提醒在代码中才能解释，干说真说不出来。

AC代码

//第三篇公共题解
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#define N 100005
using namespace std;
queue<int> q;
//bfs的队列，存储石子的序号 
vector<int> e[N];
//e[i][j]表示与第i个石子相连的第j个石子的位置 
//为什么用vector？用二维数组开会开不了这么大的，而且vector自带的函数比较好用，size，push…… 
//为什么用e？e是edge，边的意思，连接着两个点
//（多介绍一下为什么如此起变量名并非没有意义，是为了加深你的印象，下面读代码能快速反应e的含义，好像是什么心理学） 
int shijian[N];
//shijian[i]代表蝌蚪妈妈到第i个石子的用时 
//shijian=时间 因为有time函数，所以起time报错，不知道起什么好，就直接“时间”了
int pos[N];
//pos[i]代表第i秒时小蝌蚪的位置 
int vis[N];
//vis[i]代表第i个石子是否访问过
//访问过的话，时间也一定是最短的了，因为越靠前访问，到达此点的时间就是最短的，再遇到此点就不用访问了（用于降低时间复杂度） 
int flag=0;
//标记，两种情况 
void bfs(int s){//如果不写return的话，这里要返回void，不然段错误（因为这个，还debug了一会） 
    while(!q.empty()) q.pop();//清空队列，queue没有clear函数 
    q.push(s);    
    vis[s]=1;
    while(!q.empty()){//队列不空就继续，说明还有节点需要尝试访问 
        int tmp_pos=q.front();
        q.pop();
        for(int i=0;i<e[tmp_pos].size();i++){//从0循环，因为vector是从0开始push的 
            int tmp=e[tmp_pos][i];//tmp表示的是与tmp_pos相连的第i个石子的位置 
            if(vis[tmp]==0){//没访问过 
                vis[tmp]=1;//标记 
                shijian[tmp]=shijian[tmp_pos]+1;//由父节点的时间+1得到 
                q.push(tmp);//将节点入队，因为一会还要尝试去访问它的子节点            
            }            
        }
    }
}
int main(){
    int n,m,s,k;
    int s1,s2;
    while(cin>>n>>m>>k>>s){
        for(int i=0;i<m;i++)//清空vector //注意二维 
            e[i].clear();

        memset(pos,0,sizeof pos);
        memset(shijian,0,sizeof shijian);
        memset(vis,0,sizeof vis);
        flag=0;//置零 

        for(int i=1;i<=k;i++)
            cin>>pos[i];

        for(int i=1;i<=m;i++){            
            cin>>s1>>s2;
            e[s1].push_back(s2);//存储与s1相连的点是s2 
            e[s2].push_back(s1);//存储与s2相连的点是s1 
            //注意，vector只能push进去，不能用=赋值 
        } 

        bfs(s);

        for(int i=1;i<=k;i++)
            if(shijian[pos[i]]<=i){//这个<=的是i，一定注意。因为你要比较的是妈妈到第i秒小蝌蚪到达的位置是否比小蝌蚪早（或一起），要是把i改成k就起不到这样的效果了（我也错了……）
            //蝌蚪妈妈从家的位置到小蝌蚪第i秒的位置用时不超过i秒 
            //也就是说，蝌蚪妈妈能比小蝌蚪提前到达这个位置（然后等小蝌蚪就行了） 
                flag=1;//k秒之内就能找到 
                cout<<i<<endl;
                break;
            }

        if(flag==0)//k秒之内无法找到 
            cout<<shijian[pos[k]]<<endl;//蝌蚪停留在pos[k]的位置不动，输出蝌蚪妈妈到此点的最短时间 

    }
}

总结技巧

稍微总结一下，
1.vector<int> v[N]的使用，相当于一个二维数组，第一维是N，第二维是vector（无限长），意思就是有N个vector。这样来存储一些边什么的，明显优于二维数组存储，算是个比较重要且基础的技巧吧（我刚知道的）
2.分过程思考&分情况思考
（唉，我也不知道要咋想，该想不出还是想不出）
最后的最后我想问上天一句：我到底什么时候才能成为大佬啊啊啊！！！</int>