版權說明：來自 石門ss學校 Guohao OJ ,禁止轉載

題目描述

路人丁成為了一名新公交車司機，每個司機都有一張牌子，牌子的正面寫了擁有這個牌子的司機開的線路號，另外一面隨便寫了一個號碼。但是路人丁的牌子兩面寫的都不是自己開的線路號。所以他決定跟其他人換，當然，所有的司機都只有當路人丁手里的牌子上的某面寫了自己的線路號時才愿意跟他換。所以路人丁想知道自己至少要換幾次牌子才能換到一張寫有自己線路號的牌子。

輸入輸出格式

輸入格式：

第一行包括一個整數K（K≤1000），表示車的數量（新車除外）。

這些車的編號依次從1到K。接下來的K行，每行包括此車對應的線路號和牌子另一面的號碼（long long范圍的數字）。最后一行是安排路人丁開的公交車線路號以及給他的牌子上的號碼。

輸出格式：

第一行為最少交換的次數M。

接下來的M行順序輸出要交換牌子的車的編號。如果沒有方案，則輸出“IMPOSSIBLE”。

輸入輸出樣例

輸入樣例：

4 8 5 5 4 7 4 1 5 4 1 8 輸出樣例： 2 4 2

題目分析

通過題目分析我們可以發現這表面上是一道交換類題，但是如果沿著這個思路走時間復雜度讓代碼無法承受（至少對于普及組而言），我們發現一旦與一個人交換牌子就不需要再進行交換（因為如果有更優情況，為什么不在之前與他人交換呢？）

交換后我們繼承了被交換者的牌子，那我們可以把被繼承著當做自己，這就是一個 dijstra 的模板題了，另外要求輸出路徑，并且要求 字典序??，我們可以在求最短路時，順便拿一個數組記錄父節點，最后再反向輸出即可。

?

代碼

1 #include<iostream> 2 #include<fstream> 3 #include<vector> 4 using namespace std; 5 6 typedef long long LL; 7 const int Max_N=1e3+5; 8 const int Inf=(1<<31)-1; 9 10 int n; 11 LL Need; 12 LL NumF[Max_N],NumB[Max_N]; 13 14 bool vis[Max_N]; 15 LL dis[Max_N],Fa[Max_N],ea_Fa[Max_N];//dijstra 16 17 bool acc(LL A,LL B,LL C) 18 { 19 if(A==C||B==C) return 1; 20 return 0; 21 } 22 23 void dijstra(int st) 24 { 25 register int i,l; 26 dis[1]=0; 27 for(l=1;l<=n;l++){ 28 int p=-1,Min=Inf; 29 for(i=1;i<=n+1;i++) 30 if(!vis[i]&&Min>dis[i]) 31 Min=dis[i],p=i; 32 if(p==-1||vis[p]) continue; 33 vis[p]=1; 34 for(i=1;i<=n+1;i++) 35 if(!vis[i]&&acc(NumF[p],NumB[p],NumF[i])){ 36 if(dis[i]>dis[p]+1){ 37 dis[i]=dis[p]+1; 38 Fa[i]=p; 39 if(p^1) 40 ea_Fa[i]=ea_Fa[p]; 41 else 42 ea_Fa[i]=i; 43 } 44 else if(dis[i]==dis[p]+1) 45 if(ea_Fa[i]>ea_Fa[p]) 46 ea_Fa[i]=ea_Fa[p],Fa[i]=p; 47 } 48 } 49 return ; 50 } 51 52 int main() 53 { 54 scanf("%d",&n); 55 register int i,j; 56 for(i=1;i<=n+1;i++) 57 dis[i]=Inf; 58 for(i=1;i<=n;i++) 59 scanf("%lld%lld",&NumF[i+1],&NumB[i+1]); 60 scanf("%lld%lld%lld",&Need,&NumF[1],&NumB[1]); 61 // 這里是將自己裝入第一個位置，方便進行最短路操作 62 dijstra(1); 63 int p=-1,early=Inf; 64 LL res=Inf; 65 for(i=2;i<=n+1;i++) 66 if(((early>ea_Fa[i]&&res==dis[i])||res>dis[i])&&(Need==NumF[i]||Need==NumB[i])){ 67 res=dis[i]; 68 p=i; 69 early=ea_Fa[i]; 70 } 71 // 尋找最優情況 72 if(p>0&&res^Inf){ 73 printf("%lld\n",res); 74 vector<int>Ans; 75 while(Fa[p]) 76 Ans.push_back(p),p=Fa[p]; 77 for(i=Ans.size()-1;i>=0;i--) 78 printf("%lld\n",Ans[i]-1); 79 //反向輸出 80 } 81 else{ 82 printf("IMPOSSIBLE"); 83 // 不存在路到達 84 } 85 return 0; 86 } View Code

?

寫在最后的話：

題解僅供思路，要想成為 dalao ，請學會并盡量會做到教他人甚至自己寫題解。

博主（目前）是一名初二蒟蒻，如有問題還請大家指出，一起交流學習！

Happy every day!　　　　　　　　——2019.4.11

?

轉載于:https://www.cnblogs.com/lihepei/p/10756097.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的[题解]公共汽车的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。