题解 P2296 【寻找道路】

此后无良辰 · 2017-10-31 13:25:54 · 题解

spfa大法好！首先我们思考题目，他要我们连的边必须间接或直接连终点，那我们dfs从终点看看哪些点能到，记得是正向反向都存一次

，但记住我们要把那些不能到终点的再扩展一下，因为它是一些点的连边样例二的就很清楚，6不能2就不能;然后spfa！！！

#include <bits/stdc++.h>
#define inf 1000000
using namespace std;
const int maxn=200010;
struct cnm{int u;int v,w,head,next;}e[maxn],t[maxn];
int read(){
    int x=0,y=1;char c=getchar();
    while(c>'9'||c<'0'){
    if(c=='-') y=-1;c=getchar();}
    while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}    
    return x*y;}
int n,m,m1,m2,x,y,dis[maxn],h[maxn],book[maxn],vis[maxn],book1[maxn];    
void add(int u,int v,int w){
m1++;e[m1].u=u;e[m1].v=v;e[m1].w=w;e[m1].next=e[u].head;e[u].head=m1;}
void add2(int u,int v,int w){
m2++;t[m2].u=u;t[m2].v=v;t[m2].w=w;t[m2].next=t[u].head;t[u].head=m2;}//反向边
void dfs(int xx){
    if(book1[xx]) return;
    h[xx]=1;book1[xx]=1;
    for(int i=t[xx].head;i;i=t[i].next){
    int v=t[i].v;
    h[v]=1;
    dfs(v);}

}//找能到的点

void dfs1(int en)    {
    book[en]=1;
    for(int i=t[en].head;i;i=t[i].next)
    book[t[i].v]=1;}//扩展下
void spfa(int v0){
    for(int i=1;i<=n;i++) dis[i]=inf;
    queue <int> q;
    dis[v0]=0;q.push(v0);vis[v0]=1;
    while(!q.empty()){
    int u=q.front();q.pop();vis[u]=0;
    for(int i=e[u].head;i;i=e[i].next)
    {int v=e[i].v,w=e[i].w;
        if(dis[v]>dis[u]+w&&!book[v])
        {dis[v]=dis[u]+w;
        if(!vis[v]){q.push(v);vis[v]=1;}}}}}    //spfa模板
int main(){
    n=read();m=read();
    for(register int i=1;i<=m;i++)
    {int u,v,w;u=read();v=read();w=1;
    add(u,v,w);add2(v,u,w);}
    x=read();y=read();
    dfs(y);    
    if(h[x]==0) {cout<<-1<<endl;return 0;}//起点没有就-1
    for(int i=1;i<=n;i++) 
    {if(!h[i]) dfs1(i);}
    spfa(x);
    cout<<dis[y]<<endl;//输出终点的距离
return 0;}