十一届河南省赛-checkpoints(个人解法)-能AC代码
阅读原文时间:2023年07月10日阅读:2

大致题意:

zznuoj,大致题意:从A点出发达到B点去解救人质,再从B点返回到A点,经历第二遍的点只计算一次即可,AB两点不计数!求完成任务最少需要经过的点数。
大致思路:暴力!从起点到终点,和从终点到起点这两趟路其实恰好可以分开,互不影响地进行取并集计算找最佳值!
BFS枚举前1000条从起点A到终点B的路径(仅统计每种搜索的经过的点数)进set1,然后反之再搜索一次再统计一遍存进set2!然后两两求出交集后取并集最小的哪一个就是结果。
当然BFS时要舍远求近,仅保留前1000个最短的路径,两次bfs其实步骤一样——对调起点和终点即可!
优化:setmp1[N]; //可替换成bool,再开一个bool数组再进行比较。

题解:

#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
#define N 108
#define ll long long
#define mem(a,x) memset(a,x,sizeof(a)) ///peace keeper

setmp1[N]; //可替换成bool,再开一个bool数组再进行比较
setmp2[N];

vectora[N];

int n,m,A,B;
int val[N];
bool vis[N];
struct node{
int x,step; //x表示当前的走到的那个的点,step表示抵达当前点走过的步数。
bool vis[N]; //统计抵达当前点x的所有点
bool operator< (const node &p)const{ return p.stepQ;
node st,next,now;
st.x=A;st.step=;mem(st.vis,);st.vis[A]=;
Q.push(st);
int cnt=;

 while(Q.size()>){  
     now=Q.front();  
     Q.pop();  
     if(cnt>=)break ;  
     for(int i=;i<(int)a\[now.x\].size();i++){  
         int v=a\[now.x\]\[i\];  

// printf("%d->%d\n",now.x,v);
if(!now.vis[v])
{
next=now;
next.vis[v]=;

             next.x=v;next.step=now.step+;  
         ///    debug(next.vis,n);  
             if(v==B){  
                 cnt++;  
                 mp1\[cnt\].clear();  
                 for(int j=;j<=n;j++)  
                 {  
                     if(next.vis\[j\])mp1\[cnt\].insert(j);  
                 }  
                 continue;  
             }

             Q.push(next);  
         }  
     }  
 }  
 return cnt;  

}
int bfs2(int A,int B,int n){ //反向搜索一波,找寻N条最短路
queueQ;
node st,next,now;
st.x=B;st.step=;mem(st.vis,);st.vis[B]=;
Q.push(st);
int cnt=;

 while(Q.size()>){  
     now=Q.front();  
     Q.pop();  
     if(cnt>=)break ;  
     for(int i=;i<(int)a\[now.x\].size();i++){  
         int v=a\[now.x\]\[i\];  

// printf("%d->%d\n",now.x,v);
if(!now.vis[v])
{
next=now;
next.vis[v]=;
next.x=v;next.step=now.step+;
if(v==A){
cnt++;
mp2[cnt].clear();
for(int j=;j<=n;j++)
{
if(next.vis[j])mp2[cnt].insert(j);
}
continue;
}
Q.push(next);
}
}
}
return cnt;
}

int solve(int cnt1,int cnt2){

 int ans=inf;  
 for(int i=;i<=cnt1;i++){  
     for(int j=;j<=cnt2;j++){  
         set<int>mp;  
         set<int>::iterator it;  
         for(it=mp1\[i\].begin();it!=mp1\[i\].end();++it){  
             mp.insert(\*it);  
     //       printf("\[%d\] ",\*it);  
         }  
     //    cout<<" \*\*\* ";  
         for(it=mp2\[j\].begin();it!=mp2\[j\].end();++it){  
             mp.insert(\*it);  
     //        printf("(%d) ",\*it);  
         }  
         ans=min(ans,(int)mp.size());  
    //     cout<<endl;  
     }  
 }  
 return ans-;  

}

int main(){

 int T;  
 cin>>T;  
 while(T--){  
     scanf("%d%d%d%d",&n,&m,&A,&B);  
     int xi,yi;  
   //  memset(val,inf,sizeof(val));  
     for(int i=;i<=n;i++)  
         a\[i\].clear();

     for(int i=;i<=m;i++)  
     {  
         scanf("%d %d",&xi,&yi);  
         a\[xi\].push\_back(yi);  
     }  
     if(A==B){  
         printf("0\\n");continue;  
     }  
     int cnt1=bfs1(A,B,n);  
     int cnt2=bfs2(A,B,n);

     printf("%d\\n",solve(cnt1,cnt2));  
 }

 return ;  

}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章