原题网址：http://poj.org/problem?id=2457

题意：给出n条路 每条路的边权为1 求从1走到k要经过的最少的点的个数 并输出路径

最少点的个数 其实就是最短路径+1 所以我们可以把源点从1 向前移动一个单位 设为0
那么怎么去记录路径呢？
这里我们可以去开一个数组 记录当前这个点是由哪个点过来的
那么可以一直回溯 回溯到这个数组的初始化
等等 这是不是有点并查集的思想呢?
是的 确实是并查集找父节点的思想 那么我们只要把这个数组初始化 pre[i]=i 并在dijkstra中记录该点的父节点即可

#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
struct node
{
    int from,to,cost;
    node() {}
    node(int t,int q,int w):from(t),to(q),cost(w) {}
    friend bool operator <(const node &a, const node &b)
    {
        return a.cost>b.cost;
    }
};
vector<node> v[1005];
bool vis[1005];
int pre[1005];
int dis[1005];
void dijkstra(int y)
{

    priority_queue<node>q;
    q.push(node(0,1,1));///因为要输出的是点的个数 那么我们可以把0设为源点 

    while(q.size())
    {

        node now=q.top();
        q.pop();
        if(!vis[now.to])
        {
            vis[now.to]=1;
            ///下面这里十分关键 也是容易错的地方 
            ///dis和pre的赋值一定要在这里 原因的话请读者仔细思考
            pre[now.to]=now.from;///记录当前点的父节点
            dis[now.to]=now.cost;
            for(int i=0; i<v[now.to].size(); i++)
            {

                node next=now;
                next.to=v[now.to][i].to;
                if(!vis[next.to])
                {
                    next.from=now.to;
                    next.cost+=v[now.to][i].cost;
                    q.push(next);

                }
            }
        }

    }
    if(dis[y]==~0u>>1)
        puts("-1");
    else
    {
        cout<<dis[y]<<endl;
        vector<int>b;
        while(pre[y]!=y)///存路径
            b.push_back(y),y=pre[y];

        for(int i=b.size()-1; i>=0; i--)///因为路径从父节点开始走的 倒着输出
            cout<<b[i]<<endl;
    }

}
int main()
{

    int n,k;
    while(cin>>n>>k)
    {

        for(int i=0; i<=1005; i++)
            v[i].clear(),vis[i]=0,pre[i]=i,dis[i]=~0u>>1;

        int a,b;
        for(int i=1; i<=n; i++)
        {
            cin>>a>>b;
            v[a].push_back(node(a,b,1));
        }

        dijkstra(k);
    }
    return 0;
}