[题解]公共汽车

版权说明：来自石门ss学校 Guohao OJ ,禁止转载

题目描述

路人丁成为了一名新公交车司机，每个司机都有一张牌子，牌子的正面写了拥有这个牌子的司机开的线路号，另外一面随便写了一个号码。但是路人丁的牌子两面写的都不是自己开的线路号。所以他决定跟其他人换，当然，所有的司机都只有当路人丁手里的牌子上的某面写了自己的线路号时才愿意跟他换。所以路人丁想知道自己至少要换几次牌子才能换到一张写有自己线路号的牌子。

输入输出格式

输入格式：

第一行包括一个整数K（K≤1000），表示车的数量（新车除外）。

这些车的编号依次从1到K。接下来的K行，每行包括此车对应的线路号和牌子另一面的号码（long long范围的数字）。最后一行是安排路人丁开的公交车线路号以及给他的牌子上的号码。

输出格式：

第一行为最少交换的次数M。

接下来的M行顺序输出要交换牌子的车的编号。如果没有方案，则输出“IMPOSSIBLE”。

输入输出样例

输入样例：

输出样例：

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
",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
",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