poj-2457-Part Acquisition「最短路径-路

Part Acquisition

题意：

就是通过最少的交换次数，换到自己想要的东西

思路：

看作最短路径，最少距离到达目的地，不能到达输出-1；
用一个path数组记录路径。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int head[50050],cnt;
struct node
{
    int v,w;
    int nxt;
} edge[50050];
void add(int x,int y,int w)
{
    edge[++cnt].nxt=head[x];
    edge[cnt].v=y;
    edge[cnt].w=w;
    head[x]=cnt;
}
int vis[1100];
int dis[1100];
int path[1100];
int s[1100];
void Dijkstra(int x,int n)
{
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[x]=0;
    path[x]=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >qu;
    qu.push(make_pair(0,x));
    while(!qu.empty( ))
    {
        int u=qu.top( ).second;
        qu.pop( );
        if(!vis[u])
        {
            vis[u]=1;
            for(int i=head[u]; i!=-1; i=edge[i].nxt)
            {
                int v=edge[i].v;
                if(dis[v]>dis[u]+edge[i].w)//v的最小值是通过了u点才达到最小
                {
                    dis[v]=dis[u]+edge[i].w;
                    path[v]=u;//所以要输出v,必须先输出u
                    qu.push(make_pair(dis[v],v));
                }
            }
        }
    }
}
int main( )
{
    int n,k,x,y;
    memset(head,-1,sizeof(head));
    cnt=0;
    scanf("%d%d",&n,&k);
    for(int i=0; i<=k; i++)
    {
        path[i]=i;
    }
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y,1);
    }
    Dijkstra(1,k);
    if(dis[k]==INF)
    {
        printf("-1\n");
    }
    else
    {
        int cnt=0;
        // for(int i=0;i<=k;i++)
        // {
        //     cout<<path[i]<<" ";
        // }
        // cout<<endl;
        int t=k;
        int ans=0;
        while(path[t]!=t)
        {
            s[cnt++]=t;
            ans++;
            t=path[t];
        }
        printf("%d\n",ans);
        for(int i=cnt-1;i>=0;i--)
        {
            printf("%d\n",s[i]);
        }
    }
    return 0;
}