学步园

题目链接:   http://poj.org/problem?id=1847

题目大意:  这道题理解起来有点恶心

                 有N个铁轨交叉口，这些交叉口与其他交叉口通过铁轨连接

                 电车开进一个交叉口，想去另一个交叉口，必须要把灯照向下一个交叉口

                 求从A到B驾驶员需要转换灯的最小次数

解题思路:  这道题关键在于构图，每一个交叉点连接的第一条边为0

                 其他的边为1，求A到B的最短路径

       感想: 本来想找一道Dijkstra的题，试验最小二叉堆优化之后的效率

                 理解了题目发现顶点最大才100，堆的效率很难体现出来

                 而且这道题用SPFA更加方便，开始WA了几次

                 原来是入队时判断错了，写过这么多的SPFA，真不应该

                 SPFA的思想：每走一个点，修改到这个点的当前最优解，下次再准备走这点

                 时判断这次的解是不是比上一次还优？是则入队，即使到达终点也不用停止，最

                 优解总会有界限，所以当队列为空的时候，就是最优解！

代码:

//SPFA最短路模版
//入队的时候需要注意不要判断错了！
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 101
#define INF 0x3f3f3f3f
int n,m,visit[MAX],list[MAX*MAX],near[MAX],edge[MAX][MAX];

int SPFA(int A,int B)
{
    int e,s,i,v0;
    e=s=0;
    list[s++]=A;    //初始化
    visit[A]=1;
    near[A]=0;
    while(s!=e)
    {
        v0=list[e++];
        visit[v0]=0;
        for(i=1;i<=n;i++)
        {
            if(edge[v0][i]<INF&&near[v0]+edge[v0][i]<near[i])
            {
               if(!visit[i])                   //**这里最容易错误了**
               {
                    list[s++]=i;
                    visit[i]=1;
               }
                near[i]=near[v0]+edge[v0][i];  //即使队列里面有，也要改变它的值
            }
        }
    }
    return near[B];
}

int main()
{
    int i,j,k,A,B,to;
    while(scanf("%d%d%d",&n,&A,&B)!=EOF)
    {
        memset(edge,INF,sizeof(edge));
        memset(near,INF,sizeof(near));
        memset(visit,0,sizeof(visit));
        for(i=1;i<=n;i++)            //构图过程
        {
            scanf("%d",&m);
            for(j=1;j<=m;j++)
            {
                scanf("%d",&to);
                if(j==1)
                    edge[i][to]=0;   //第一条边为0
                else
                    edge[i][to]=1;   //其余的边为1
            }
        }
        if(A==B)     //终点和起点一样，直接输出
        {
            printf("0\n");
            return 0;
        }
        k=SPFA(A,B);
        if(k==INF)   //不可到达B点
            printf("-1\n");
        else
            printf("%d\n",k);
    }
    return 0;
}

注：原创文章，转载求注明出处