Description
输入一个无向图，指定一个顶点s开始bfs遍历，求出s到图中每个点的最短距离。
如果不存在s到t的路径，则记s到t的距离为-1。
Input
输入的第一行包含两个整数n和m，n是图的顶点数，m是边数。1<=n<=1000，0<=m<=10000。
以下m行，每行是一个数对v y，表示存在边(v,y)。顶点编号从1开始。
Output
记s=1，在一行中依次输出：顶点1到s的最短距离，顶点2到s的最短距离，...，顶点n到s的最短距离。
每项输出之后加一个空格，包括最后一项。
Sample Input
5 3
1 2
1 3
2 4
Sample Output
0 1 1 2 -1
//Dijiskra algorithm
#include<iostream>
#include<memory>
#include<algorithm>
using namespace std; const int MAX = 1005;
const int INF = 0x3f3f3f3f; int n, m;
int d[MAX];
bool v[MAX];
int edge[MAX][MAX]; void Dijiskra(int start)
{
//initial
memset(v, false, sizeof(v));
for(int i=1;i<MAX;i++)
d[i]=INF; //start at node 'Start'
d[start]=0;
for(int i=1;i<=n;i++)
{
int temp;
int minx = INF;
for(int j=1;j<=n;j++)
{
if(!v[j]&&d[j]<minx)
{
temp=j;
minx=d[j];
}
}
v[temp]=true; //refresh distance array
for(int k=1;k<=n;k++)
d[k]=min(d[k], d[temp]+edge[temp][k]);
}
} int main()
{
cin>>n>>m;
memset(edge, INF, sizeof(edge));
for(int i=0;i<m;i++)
{
int a, b;
cin>>a>>b;
edge[a][b]=1;
edge[b][a]=1;
} Dijiskra(1); for(int i=1;i<=n;i++)
{
if(d[i]==INF)cout<<-1<<" ";
else cout<<d[i]<<" ";
}
cout<<endl; return 0;
}