PTA | 程序设计类实验辅助教学平台
题解：
bfs可以求解从根节点到叶子节点的指定路径，这里的vis[]不是为了防止访问到父节点，更多的是为了缩小路径长度，mpp和mp的映射也很巧妙，开始我用的还是map<pair,差点没麻烦死
#includeusing namespace std;const int N=1e4+10;bool vis[N];//虽然是有向图，但是必要int n,idx;vectorp[N];mapmp;mapmpp;int pre[N];//记录路径vectorbfs(int s,int e){pre[e]=-1;queueq;q.push(s);memset(vis,0,sizeof vis);vis[s]=1;while(q.size()){int x=q.front();if(x==e)break;q.pop();for(int i=0;i<p[x].size();i++){if(vis[p[x][i]])continue;vis[p[x][i]]=1;q.push(p[x][i]);pre[p[x][i]]=x;}}vectort;if(pre[e]==-1)return t;while(e!=s){t.push_back(e);e=pre[e];}t.push_back(s);reverse(t.begin(),t.end());return t;}int main(){cin>>n;for(int i=0;i>s1>>id1>>s2>>id2;if(mp.count(s1+" 0")==0){mpp[idx]=s1+" 0";mp[s1+" 0"]=idx++;mpp[idx]=s1+" 1";mp[s1+" 1"]=idx++;}if(mp.count(s2+" 0")==0){mpp[idx]=s2+" 0";mp[s2+" 0"]=idx++;mpp[idx]=s2+" 1";mp[s2+" 1"]=idx++;}s1+=" "+id1;s2+=" "+id2;p[mp[s1]].push_back(mp[s2]);}vectorans(2020)//定义了一个容量为2020的vector，且里面每个值为0;for(int i=0;i<idx;i+=2){vectors1=bfs(i,i+1);vectors2=bfs(i+1,i);if(ans.size()>s1.size()&&s1.size()>0){ans=s1;}if(ans.size()>s2.size()&&s2.size()>0){ans=s2;}}for(int i=0;i