大致题意:
zznuoj,大致题意:从A点出发达到B点去解救人质,再从B点返回到A点,经历第二遍的点只计算一次即可,AB两点不计数!求完成任务最少需要经过的点数。
大致思路:暴力!从起点到终点,和从终点到起点这两趟路其实恰好可以分开,互不影响地进行取并集计算找最佳值!
BFS枚举前1000条从起点A到终点B的路径(仅统计每种搜索的经过的点数)进set1,然后反之再搜索一次再统计一遍存进set2!然后两两求出交集后取并集最小的哪一个就是结果。
当然BFS时要舍远求近,仅保留前1000个最短的路径,两次bfs其实步骤一样——对调起点和终点即可!
优化:set
题解:
#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
set
set
vector
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.step
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条最短路
queue
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 ;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章