题目大意

输入数据在第一行给出n和m，表示有n个交易方式，m种商品。

接下来n行，每行一个a,b，表示可以用a换b（不可逆）

你现在有1号商品，问最少需要多少次交易才能换到m号商品。输出次数和交易方案。

 

这题也是显然可以看出的最短路，不过这次不是走路，而是交易而已。我们可以将商品想象成点，交易方式想象成边（单向），代价为1，这样就和最短路问题一样了。

唯一有点意思的是询问方案。我们更新一个点的时候，保存是谁更新他（用谁换到它），然后反向找就可以了。

代码

#include
      
       #include
       
        #include
        
         struct qq{    int x,y,next;}a[50005];struct qqq{    int c,last;}f[2005];int first[2005];bool tf[2005];int q[2005];int n,k,len=0;void make_l(int x,int y){    len++;    a[len].x=x;    a[len].y=y;    a[len].next=first[x];    first[x]=len;}void find(int x){    if(f[x].last!=-1)find(f[x].last);    printf("%d\n",x);}int main(){    scanf("%d %d",&n,&k);    memset(first,0,sizeof(first));    for(int i=1;i<=n;i++)    {        int x,y;        scanf("%d %d",&x,&y);        make_l(x,y);    }    int head=1,tail=2;    for(int i=1;i<=k;i++)    {        f[i].c=999999999;        f[i].last=-1;    }    memset(tf,false,sizeof(tf));    q[head]=1;tf[1]=true;    f[1].c=1;    while(head!=tail)    {        int x=q[head];        for(int i=first[x];i!=0;i=a[i].next)        {            int y=a[i].y;            if(f[y].c>f[x].c+1)            {                f[y].c=f[x].c+1;                f[y].last=x;//对于输出方案，我们存储是谁交换到y，求解释反向找，见find函数                if(tf[y]==false)                {                    tf[y]=true;                    q[tail]=y;tail++;                    if(tail>n)tail=1;                }            }        }        tf[x]=false;        head++;        if(head>n)head=1;    }    if(f[k].c==999999999)printf("-1\n");        //唯一要注意的是无解的情况      else {printf("%d\n",f[k].c);find(k);}}