题解 P2296 【寻找道路】

· · 题解

这道题其实就是一道最短路的模板题。

step1:根据路线的第一个要求，只需要将形如下面形式的点删去，再求起点到终点的最短路即可。

什么点该删：

1：出度为零但不为终点的点。
2：直接连向上述（1）类型点的点。

step2:只需求单源最短路就可以AC了。

下面附上本人AC代码：

#include<bits/stdc++.h>
using namespace std;
int a,b;
vector<int> v[10009];
vector<int> va[10009];
int vi[10009];
int vt[10009];
queue<int> q;
int main(){
    memset(vi,0,sizeof(vi));
    memset(vt,127,sizeof(vt));
    cin>>a>>b;
    for(int i=0;i<b;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        va[y].push_back(x);
    }
    int s,t;
    cin>>s>>t;
    for(int i=1;i<=a;i++){//删点操作
        if(v[i].size()==0&&i!=t){
            for(int j=0;j<va[i].size();j++){
                vi[va[i][j]]=1;
            }
        }
    }
    q.push(s);
    vt[s]=0;
    while(!q.empty()){//spfa
        for(int i=0;i<v[q.front()].size();i++){
            if(vi[v[q.front()][i]]==0){
                if(vt[v[q.front()][i]]>vt[q.front()]+1){
                    vt[v[q.front()][i]]=vt[q.front()]+1;
                    q.push(v[q.front()][i]);
                }
            }
        }
        q.pop();
    }
    if(vt[t]>99999999){//别忘输出-1
        cout<<-1;
    }else{
        cout<<vt[t];
    }
}

本题很善良，什么都不卡。