描述
在TZC，WY存了钱，现在他要去买东西了。店很多，标记为1，2，3，4，5，6....但有的店之间有大路相连，而有的没有路。现在要由一个店到另一个店买东西，中途最少要经过多少个其它的店铺呢?
如图例，如果他从1开始到5，那么至少要经过1个店铺，从1到4至少要经过2个店铺。
输入
输入数据有多组，每组的第一行是两个正整数n, k(1<=n<=1000, 1<=k<=2000)，接下来有k行，每行有两个正整数a, b(1 <= a, b <= n)，表示店铺a和b之间有路相连，接下来一行为两个正整数p和q分别代表起始店铺。当n, k输入都为0时结束。
输出
输出从店铺p到店铺q之间最少要经过的其它的店铺的数目。如果从p无法到达q，则输出"No solution"。
样例输入
6 6
1 4
1 2
2 3
3 4
5 4
5 6
1 6
0 0
样例输出
2
解题思路：BFS+记录步数
菜鸡的成长史 ^-^
#include <bits/stdc++.h>
using namespace std;
const int N=;
vector<int> G[N];
int n,m,vis[N];
struct Node
{
int B;
int S;
}p,q;
void bfs(int start,int ending)
{
int flag=;
queue<Node> que;
p.S=,p.B=start;
que.push(p);
while(!que.empty())
{
q=que.front(),que.pop();
int u=q.B,w=q.S;
if(vis[u]) continue;
vis[u]=;
for(auto X:G[u])
{
q.B=X,q.S=w+;
if(q.B==ending) {cout << q.S- << endl,flag=;break;}
que.push(q);
}
if(flag==) break;
}
if(flag==) cout << "No solution" << endl;
while(!que.empty()) que.pop();
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>n>>m&&(n+m))
{
int d1,d2;
while(m--){
cin>>d1>>d2;
G[d1].push_back(d2),G[d2].push_back(d1);
} //建图
int start,ending;
cin>>start>>ending;
memset(vis,,sizeof(vis)); //标记
bfs(start,ending);
for(int i=;i<=n;i++) G[i].clear(); //注意清楚
}
return ;
}