题目描述

给定无权无向图 G(V,E) 和源点s/终点t，求 s->t 的最短路径。

假设读入边的列表是有（字典）序的（既邻接表就是有序的）。

输入格式

第一行包含 4 个整数N、M、s、t（N≤5000，M≤200000），表示该图共有N个结点和M条无向边。起点为s，终点为t。

接下来 M 行，每行包含 2 个整数{u,v}，表示有一条无向边连接结点u、v。

输出格式

输出最短路的长度。

若无法到达，输出"No path"（不含引号）。

样例输入

4 3 1 4
1 2
1 3
2 4

样例输出

2

代码如下：

#include <iostream>
#include<queue>
using namespace std;
bool a[5001][5001];
bool vis[5001];
int d[5001];
int n,m,s,t;
void bfs()
{
	queue<int>q;
	q.push(s);
	d[s] = 0;
	vis[s] = 1;
	while(!q.empty())
	{
		int k = q.front();
		q.pop();
		for(int i=1;i<=n;i++)
		{
			if(a[k][i] && !vis[i])
			{
				vis[i] = 1;
				d[i] = d[k] + 1;
				if(i==t) return ;
				q.push(i);
			}
		}
	}
}
int main()
{
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		a[u][v] = a[v][u] = 1;
	}
	bfs();
	if(d[t] != 0)
	{
		cout<<d[t];
	}
	else
	{
		cout<<"No path";
	}
	return 0;
}