题号：P2296
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include<iostream> #include<cstring> #include<queue> #define MapLoop(e,node) for(int e=first[node];e!=-1;e=_next[e]) #define MapLoopRvs(e,node) for(int e=first_rvs[node];e!=-1;e=_next_rvs[e]) using namespace std; int n,m,s,t; int first[10005],u[200005],v[200005],_next[200005];//两个图，一个正图，一个反图 int first_rvs[10005],u_rvs[200005],v_rvs[200005],_next_rvs[200005]; int _distance[10005]; bool OK[10005],OK2[10005]; bool visited[10005]; bool inqueue[10005]; queue<int> q,q1; void bfs(int node){//反图用来遍历与终点不联通的点 q1.push(node); visited[node]=true; OK[node]=true; while(!q1.empty()){ int cur=q1.front(); q1.pop(); OK[cur]=true; MapLoopRvs(e,cur){ if(!visited[v_rvs[e]]){ visited[v_rvs[e]]=true; q1.push(v_rvs[e]); } } } memcpy(OK2,OK,sizeof(OK));//将与终点不联通的点的邻接点全部删除 for(int i=1;i<=n;i++){ if(OK[i]==false){ MapLoopRvs(e,i){ OK2[v_rvs[e]]=false; } } } memcpy(OK,OK2,sizeof(OK)); } void SPFA(){//SPFA求最短路 int cnt=0; memset(_distance,0x7f,sizeof(_distance)); q.push(s); _distance[s]=0; inqueue[s]=true; while(!q.empty()){ int cur=q.front(); q.pop(); inqueue[cur]=false; MapLoop(e,cur){ if(_distance[v[e]]>_distance[u[e]]+1&&OK[v[e]]){//注意只能要没有删去的点 _distance[v[e]]=_distance[u[e]]+1; if(!inqueue[v[e]]){ inqueue[v[e]]=true; q.push(v[e]); cnt++; } } } } } int main(){ ios::sync_with_stdio(false); memset(first,-1,sizeof(first)); memset(first_rvs,-1,sizeof(first_rvs)); cin>>n>>m; for(int i=1;i<=m;i++){ cin>>u[i]>>v[i]; v_rvs[i]=u[i]; u_rvs[i]=v[i]; if(u[i]==v[i]){ i--; m--; continue; } _next[i]=first[u[i]]; first[u[i]]=i; _next_rvs[i]=first_rvs[u_rvs[i]];//建反图 first_rvs[u_rvs[i]]=i; } cin>>s>>t; bfs(t); SPFA(); if(_distance[t]>1e9)cout<<"-1"; else cout<<_distance[t]; } |