poj 2457 Part Acq…

題意：cows 想用自己手上的商品（1）通過多次交換得到想要的商品（k），給出兩種商品的交換關系，求出至少有多少種商品經過交換，輸出交換的順序。

思路：最短路。相當于求從1商品到k商品的最短路徑，中間再記錄一下結點資訊。我用的是邊表實作dij算法

//412K      79MS

#include

#include

const int EM = 50010;

const int VM = 1005;

const int inf = 0x3f3f3f3f;

struct Edge

{

      int frm,to,nxt;

}edge[EM];

int head[VM],vis[VM],dis[VM],pre[VM];

int e,n,sta,end,ans;

bool mark;

void addedge(int cu,int cv)

{

      edge[e].frm = cu;

      edge[e].to = cv;

      edge[e].nxt = head[cu];

      head[cu] = e ++;

}

void print(int tmp)//輸入路徑

{

      ++ans;

      if (tmp != -1)

              print(pre[tmp]);

      if (tmp == -1)

              return ;

      if (!mark)

      {

              printf ("%d\n",ans);

              mark = true;

      }

      printf ("%d\n",tmp);

}

void Dij()

{

      int i;

      memset (vis,0,sizeof(vis));

      memset (dis,0x3f,sizeof(dis));

      memset (pre,-1,sizeof(pre));

      for (i = head[sta];i != -1;i = edge[i].nxt)

      {

              dis[edge[i].to] = 1;

              pre[edge[i].to] = sta;

      }

      pre[sta] = -1,vis[sta] = 1;

      int cnt = n - 1;

      while (cnt --)

      {

              int min = inf;

              int flag;

              for (i = 1;i <= end;i ++)

                      if (!vis[i]&&dis[i] < min)

                              flag = i,min = dis[i];

              vis[flag] = 1;

              for (i = head[flag];i != -1;i = edge[i].nxt)

              {

                      int v = edge[i].to;

                      if (!vis[v]&&dis[v]>dis[flag]+1)

                      {

                              dis[v] = dis[flag] + 1;

                              pre[v] = flag;              //v的前驅是flag

                      }

              }

      }

      if (dis[end] == inf) //無路徑

              printf ("-1\n");

      else

      {

              mark = false;

              ans = -1;

              int tmp = end;

              print(tmp);

      }

}

int main ()

{

      while (~scanf ("%d%d",&n,&end))

      {

              e = 0;

              sta = 1;

              memset (head,-1,sizeof(head));

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

              {

                      int u,v;

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

                      addedge(u,v);

              }

              Dij();

      }

      return 0;

}