小哼和小哈一同坐飞机去旅游，他们现在位于1号城市，目标是5号城市，可是1号城市并没有直接到5号城市的直航. 不过小哼已经收集到了很多航班的信息，现在小哼希望找到一中乘坐方式，使得转机的次数最少？



思路：

这里用了图的邻接矩阵来储存地图。数组的第i行第j列表示的就是顶点i到顶点j是否有边。1表示有边，∞表示没有边，自己到自己（即i==j）设为0。

代码：

#include<iostream>
#include<cstdio>
#include<cstring> 
#define INF 99999999
typedef struct note note;
struct note
{
    int x;//城市编号
    int s;//转机方向
};
note que[2501]; //存储图   标记数组
int e[51][51],book[51];
int main()
{
    int head,tail;
    int i,j,n,m,a,b,cur,start,end,flag = 0;
    scanf("%d %d %d %d",&n,&m,&start,&end);//n是节电个数，m是节点之间边的个数，start和end是起点和终点
    for(i = 1; i <= n; ++i)//初始化地图
        for(j = 1; j <= n; ++j)
            if(i == j) e[i][j] = 0;
            else e[i][j] = INF;
    for(i = 1; i <= m; ++i)//输入地图
    {
        scanf("%d %d",&a,&b);
        e[a][b] = 1;
        e[b][a] = 1;
    }
    head = 1;
    tail = 1;
    que[tail].x = start;//第一个城市入队
    que[tail].s = 0;
    tail++;
    book[start] = 1;
    while(head < tail)
    {
        cur = que[head].x;
        for(j = 1; j <= n; ++j)
        {
            if(e[cur][j] != INF && book[j] == 0)
            {
                que[tail].x = j;
                que[tail].s = que[head].s + 1;
                tail++;
                book[j] = 1;
            }
            if(que[tail].x == end)
            {
                flag = 1;
                break;
            }
        }
        if(flag == 1)
            break;
        head++;
    }
    printf("%d",que[tail-1].s);
    return 0;
}