main.c

来自「邮递员*** ：两点之间的最短距离」· C语言 代码 · 共 86 行

#include <stdio.h>
#include <string.h>
int n,k;
struct edge
{
        int to;
        edge*next;
} *pool;
int ce;
int p,q;
edge *edges[20000];
bool visited[20000];
edge* newEdge(int t,edge* next)
{
        pool[ce].to=t;
        pool[ce].next=next;
        return pool+(ce++);
}
void clearEdge()
{
        ce=0;
        memset(edges,0,sizeof(edges));
        memset(visited,0,sizeof(visited));
}
struct pairab
{
        int node;
        int length;
};
bool bfs(int& ret)
{
        pairab dqueue[40000];
        int top=0,bot=0;
        dqueue[top].node=p;
        dqueue[top++].length=0;
        visited[p]=true;
        while (bot<top)
        {
                pairab curr=dqueue[bot++];
                if(curr.node==q)
                {
                        ret=curr.length;
                        return true;
                }
                for(edge* i=edges[curr.node];i;i=i->next)
                {
                        if(!visited[i->to])
                        {
                                visited[i->to]=true;
                                dqueue[top].node=i->to;
                                dqueue[top++].length=curr.length+1;
                        }
                }
        }
        return false;
}
int main()
{
        pool=new edge[40000];
        while(scanf("%i%i",&n,&k),n)
        {
                clearEdge();
                for(int i=0;i<k;i++)
                {
                        int a,b;
                        scanf("%d%d",&a,&b);
                        --a;
                        --b;
                        edges[a]=newEdge(b,edges[a]);
                        edges[b]=newEdge(a,edges[b]);
                }
                scanf("%d%d",&p,&q);
                p--;
                q--;
                int r;
                if(p==q)
                        puts("0");
                else if(bfs(r))
                {
                        printf("%d\n",r-1);
                }
                else
                        puts("No solution");
        };
        delete[] pool;
}