题解 P2296 【寻找道路】

Vimpire_D · 2017-09-02 10:44:51 · 题解

//前面傻了,road数组开小了,应该是要对应m的范围.

//下面说一下我的思路吧,这道题是有条件的最短路问题,那么我们只需要在满足条件上的点进行最短路即可

//那么这么找满足条件的点呢,先在循环中就标记每个点的出度,我们现在终点进行一次bfs,经过一个点那么它的num数组++,也就是标记一下它的入度,那么spfa时满足条件的点就是出度等于入度的点~~是不是感觉很简单,下面是我的代码了

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <queue>
using namespace std;
const int INF=100000111;
int n,m,s,t,tail,vis[350001],head1[350001],head2[350001],sign[350001],inqueue[350001],chu[350001],num[350001];
struct node {
    int u,v,next;
};
node r1[350001],r2[350001];
queue<int>q;
void add(int x,int y) {
    r1[++tail].u=x;
    r1[tail].v=y;
    r1[tail].next=head1[x];
    head1[x]=tail;
    r2[tail].u=y;
    r2[tail].v=x;
    r2[tail].next=head2[y];
    head2[y]=tail;
}
void bfs(int sx) {             
    q.push(sx);
    sign[sx]=1;
    while (!q.empty()) {
        int sx=q.front();
        q.pop();
        for (int i=head2[sx];i;i=r2[i].next) {
            int nex=r2[i].v;
            num[nex]++; 
            if (!sign[nex]) {
                sign[nex]=1;
                q.push(nex);
            }
        }
    }
}
void spfa(int sx,int sy) {
    for (int i=1;i<=n;i++)
        vis[i]=INF;
    q.push(sx);
    inqueue[sx]=1;
    vis[sx]=0;
    while (!q.empty()) {
        int sx=q.front();
        q.pop();
        for (int i=head1[sx];i;i=r1[i].next) {
            int nex=r1[i].v;
            if (vis[sx]+1 < vis[nex] && num[nex]==chu[nex]) {
                vis[nex]=vis[sx]+1;
                if (!inqueue[nex]) {
                    inqueue[nex]=1;
                    q.push(nex);
                }
            }
        }
    } 
    if (vis[sy] == INF) printf("-1"); 
    else printf("%d",vis[sy]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        chu[x]++;
    }
    scanf("%d%d",&s,&t);
    bfs(t);
    spfa(s,t);
    return 0;
}