Bzoj 1674: [Usaco2005]Part Acquisition dijkstra,堆

1674: [Usaco2005]Part Acquisition

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 337 Solved: 162
[Submit][Status][Discuss]

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).

Sample Input

6 5 //6个星球,希望得到5,开始时你手中有1号货物.
1 3 //1号星球,希望得到1号货物,将给你3号货物
3 2
2 3
3 1
2 5
5 4

Sample Output

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.

HINT

Source

Silver

题解：

dijkstra+堆优化。

连边，跑最短路。。。

 #include<bits/stdc++.h>

 using namespace std;

 #define INF 1e9

 #define MAXK 1010

 #define MAXN 50010

 struct node

 {

     int begin,end,value,next;

 }edge[MAXN];

 int cnt,Head[MAXK],dis[MAXK],SIZE=,Heap[MAXK],K,pos[MAXK];

 void addedge(int bb,int ee,int vv)

 {

     edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;

 }

 int read()

 {

     int s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 void Push1(int k)

 {

     int now=k,root;

     while(now>)

     {

         root=now/;

         if(dis[Heap[root]]<=dis[Heap[now]])return;

         swap(Heap[root],Heap[now]);

         swap(pos[Heap[root]],pos[Heap[now]]);

         now=root;

     }

 }

 void Insert(int k)

 {

     Heap[++SIZE]=k;pos[k]=SIZE;Push1(SIZE);

 }

 void Pop1(int k)

 {

     int now,root=k;

     pos[Heap[k]]=;Heap[k]=Heap[SIZE--];if(SIZE>)pos[Heap[k]]=k;

     while(root<=SIZE/)

     {

         now=root*;

         if(now<SIZE&&dis[Heap[now+]]<dis[Heap[now]])now++;

         if(dis[Heap[root]]<=dis[Heap[now]])return;

         swap(Heap[root],Heap[now]);

         swap(pos[Heap[root]],pos[Heap[now]]);

         root=now;

     }

 }

 int dijkstra(int start)

 {

     int i,u,v;

     for(i=;i<=K;i++)dis[i]=INF;dis[start]=;

     for(i=;i<=K;i++)Insert(i);

     while(SIZE>)

     {

         u=Heap[];Pop1(pos[u]);

         for(i=Head[u];i!=-;i=edge[i].next)

         {

             v=edge[i].end;

             if(dis[u]+edge[i].value<dis[v]){dis[v]=dis[u]+edge[i].value;Push1(pos[v]);}

         }

     }

     return dis[K];

 }

 int main()

 {

     int n,bb,ee,i,ans;

     n=read();K=read();

     memset(Head,-,sizeof(Head));cnt=;

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

     {

         bb=read();ee=read();addedge(bb,ee,);

     }

     ans=dijkstra();

     if(ans==INF)printf("-1");

     else printf("%d",ans);

     return ;

 }

秒客网