注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

URAL1096[Get the right route plate!]  

2010-04-15 16:53:34|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

水水的BFS,注意图是有向的。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-15

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

 

#define MAXNODE 2000

 

int K;

int map[MAXNODE][MAXNODE];

int T;

int S1,S2;

 

int main()

{

    scanf("%d\n",&K);

    for (int i=1;i<=K;i++)

    {

        int u,v;

        scanf("%d %d\n",&u,&v);

        map[u-1][v-1]=i;

    }

    scanf("%d %d %d\n",&T,&S1,&S2);

   

    bool inq[MAXNODE];

    int q[MAXNODE];

    int open=0,close=0;

    int dis[MAXNODE];

    int pre[MAXNODE];

    memset(inq,false,sizeof(inq));   

    inq[q[open++]=S1-1]=true;

    pre[S1-1]=S1-1;

    dis[S1-1]=0;

    inq[q[open++]=S2-1]=true;

    pre[S2-1]=S2-1;

    dis[S2-1]=0;

    while (close<open)

    {

          int now=q[close++];

          for (int i=0;i<MAXNODE;i++)

              if (map[now][i]&&!inq[i])

              {

                 inq[q[open++]=i]=true;

                 pre[i]=now;

                 dis[i]=dis[now]+1;

              }

    }

    if (inq[T-1])

    {

       printf("%d\n",dis[T-1]);       

       int s[MAXNODE];

       int top=0;

       int u=T-1;

       while (pre[u]!=u)

             u=pre[s[top++]=u];

       s[top++]=u;

       for (int i=top-1;i>0;i--)

           printf("%d\n",map[s[i]][s[i-1]]);

    }

    else printf("IMPOSSIBLE\n");

    return 0;

}

 

 

  评论这张
 
阅读(140)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018