POJ 2457 Part Acquisition【Dij+記錄路徑】

Part Acquisition

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 4128	Accepted: 1767	Special Judge

Description

The cows have been sent on a mission through space to acquire a new milking machine for their barn. They are flying through a cluster of stars containing N (1 <= N <= 50,000) planets, each with a trading post. 

The cows have determined which of K (1 <= K <= 1,000) types of objects (numbered 1..K) each planet in the cluster desires, and which products they have to trade. No planet has developed currency, so they work under the barter system: all trades consist of each party trading exactly one object (presumably of different types). 

The cows start from Earth with a canister of high quality hay (item 1), and they desire a new milking machine (item K). Help them find the best way to make a series of trades at the planets in the cluster to get item K. If this task is impossible, output -1.

Input

* Line 1: Two space-separated integers, N and K. 

* Lines 2..N+1: Line i+1 contains two space-separated integers, a_i and b_i respectively, that are planet i's trading trading products. The planet will give item b_i in order to receive item a_i.

Output

* Line 1: One more than the minimum number of trades to get the milking machine which is item K (or -1 if the cows cannot obtain item K). 

* Lines 2..T+1: The ordered list of the objects that the cows possess in the sequence of trades.

Sample Input

6 5

1 3

3 2

2 3

3 1

2 5

5 4

Sample Output

4

1

3

2

5

Hint

OUTPUT DETAILS: 

The cows possess 4 objects in total: first they trade object 1 for object 3, then object 3 for object 2, then object 2 for object 5.

Source

USACO 2005 February Silver

題目大意：有n條邊，K個點，我們的目的是從1作為源點，K作為終點，求一條從1-k的最短路，并輸出路徑，如果沒有邊能從1走到K，那麼輸出-1.

思路：

1、N比較大，K 反而比較小，我們采用dijkstra算法來求最短路，1000*1000對于1000ms來說微不足道。

2、記錄路徑問題，我們設定path【i】=x，表示點i作為終點的最短路徑從x點走過來，也就是說，在松弛的時候：dis【v】=dis【u】+map【u】【v】的時候，我們設定path【v】=u，每次都随着更新，path【v】裡邊的u一定是最後一次松弛的點。這樣，我們在初始的時候，将path【1-k】都設定為值-1，然後我們一直使得now=path【now】，然後記錄now即可。

AC代碼：

#include<stdio.h>
#include<string.h>
using namespace std;
int head[1000000];
struct EdgeNode
{
    int from;
    int to;
    int next;
    int w;
}e[1000000];
int vis[1000000];
int dis[1000000];
int path[1000000];
int ans[1000000];
int n,m,cont;
void add(int from,int to,int w)
{
    e[cont].from=from;
    e[cont].w=w;
    e[cont].to=to;
    e[cont].next=head[from];
    head[from]=cont++;
}
void Dij()
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)path[i]=-1;
    for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f;
    dis[1]=0;
    for(int i=0;i<n;i++)
    {
        int u=-1;
        int tmp=0x3f3f3f3f;
        for(int j=1;j<=n;j++)
        {
            if(vis[j]==0&&tmp>dis[j])
            {
                u=j;
                tmp=dis[j];
            }
        }
        vis[u]=1;
        for(int k=head[u];k!=-1;k=e[k].next)
        {
            int v=e[k].to;
            int w=e[k].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                path[v]=u;
            }
        }
    }
    if(dis[n]==0x3f3f3f3f)
    {
        printf("-1\n");
        return ;
    }
    int tot=0;
    ans[tot++]=n;
    int now=n;
    while(1)
    {
        now=path[now];
        if(now==-1)break;
        ans[tot++]=now;
    }
    printf("%d\n",tot);
    for(int i=tot-1;i>=0;i--)
    {
        printf("%d\n",ans[i]);
    }
}
int main()
{
    while(~scanf("%d%d",&m,&n))
    {
        cont=0;
        memset(head,-1,sizeof(head));
        for(int i=0;i<m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y,1);
        }
        Dij();
    }
}