problem:Part Acquisition
題目描述：
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.
給出N條邊，單向的。再給出數字K.問從1号點到K點号，最短路上經過多少個點。
輸入格式：
- 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.
輸出格式：
- 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).
樣例輸入：
6 5
1 3
3 2
2 3
3 1
2 5
5 4
樣例輸出：
4
我們先得把輸入格式翻譯一下：
*第1行：兩個以空格分隔的整數，N和K.
*第2…N + 1行：第i + 1行包含兩個空格分隔的整數，a_i和b_i，分别是行星i的交易交易産品。行星将給出項目b_i以便接收項目a_i。
看到這，我們就可以畫樣例圖了：
這就是這題給的樣例：
（注意，這題他的連線是單向的）
從1到5經過了：1----3----2----5四個點，是以答案是4.
那我們想想，這個題目怎麼做呢？想一下上篇部落格寫的方法，費洛伊德算法可以做出來嗎？（詳見https://blog.csdn.net/qq_42884520/article/details/86678329），答案應該是不行的，至少本蒟蒻是做不出的 ，因為費洛伊德算法常針對的是雙向的線，而此題是單向的，是以我們得想其它的方法了：沒錯，這就是今天要使用的Dijkstra算法，那什麼是Dijkstra算法呢？讓我們查查百度百科：(https://baike.baidu.com/item/迪傑斯特拉算法/4049057?fromtitle=Dijkstra算法&fromid=215612&fr=aladdin)
看完後是不是一臉懵比？沒事，讓我們看看一個例子就好啦嗎：
我們看看這個圖，我們怎麼辦，很簡單，我們寫一個循環，第一輪先把dis[1]打上标記：做一個替換 dis[2]=2,dis[3]=4,dis[4]=7;
第二輪我們把dis[2]打上标記，使得：dis[3]=2+1=3 dis[5]=2+2=4;
第三輪把dis[3]打上标記：使得：dis[4]=4;
接下來的循環把4,5都打上标記，這樣，整個圖的最短路徑都能求出來啦
但是這個方法不能用來處理帶有負數的值，不然就會産生錯誤答案，不信自己去推一推。
這個算法的思想是什麼呢：
就是從一個點出發，到一個點的最短路徑必然會經過一個中轉點，我們隻要求出中轉點的最短路徑，答案就顯而易見了。
代碼實作：
（設起點為s，pre[v]為v的前驅節點，用來輸出路徑）
1.初始化：dis[v]=0x7f,dis[s]=0;pre[s]=0;
2.for(int i=1;i<=n;i++)
1.找一個未通路過的u點，使得dis[u]最小；
2.标記u
3.for與u相連的每個未确定最短路徑的頂點v。
if(dis[u]+w[u][v]<dis[v])
{
dis[v]=dis[u]+w[u][v];
pre[v]=u;
}
3.結束。
有了以上這些基礎，在重新回去看看題，相信你可以做出來的
下面附上AC代碼和解析：
#include<cstdio>
#include<iostream>
#define INF 10000005
using namespace std;
int map[1005][1005],dis[1005],path[1005],vis[1005];
int n,k;
void read(int &x)
{
char ch;
bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar());
if(ok) x=-x;
}
void dijkstra()
{
for(int i=1;i<=k;i++)
{
dis[i]=map[1][i];
if(i!=1&&map[1][i]<INF) //記錄目前能到達的點的前驅
path[i]=1;
}
vis[1]=1;
int min,v;
for(int i=1;i<k;i++)
{
min=INF;
v=1;
for(int j=1;j<=k;j++)
{
if(!vis[j]&&dis[j]<min)
{
min=dis[j];
v=j;
}
}
vis[v]=1;
for(int j=1;j<=k;j++)
{
if(!vis[j]&&dis[j]>dis[v]+map[v][j])
{
dis[j]=dis[v]+map[v][j];
path[j]=v; //記錄到達j點的最短路徑的前驅
}
}
}
}
int main()
{
read(n);read(k);
for(int i=1;i<=k;i++)
{
for(int j=1;j<=k;j++)
{
//對vis數組,path數組,map數組進行初始化
map[i][j]=INF;
}
vis[i]=0;
path[i]=-1;
}
int u,v;
for(int i=1;i<=n;i++)
{
read(u);read(v);
map[u][v]=1; //因為要計算通過的頂點的個數，是以把map初始化1
}
dijkstra();
if(dis[k]==INF)
{
//判斷兩點間是否能夠到達
printf("-1\n");
}
else
{
printf("%d\n",dis[k]+1); //輸出需要經過的頂點的個數 ，頂點數是邊的數目加1
}
return 0;
}
謝謝各位大佬的觀看，謝謝，謝謝。