日度归档：28 7 月, 2017

洛谷 寻找道路

发表评论

题号：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];
}