将图反向，从终点spfa，把和终点没有联系的点找出来，

把它们和它们所连接的所有点删去（反向图）

然后再一遍spfa，输出最短路即可

 

代码：

#include
     
      #include
      
       #include
       
        #define MAXM 200005#define MAXN 10005#define INF 0x3f3f3f3fusing namespace std;int n,m;struct edge{    int to,next,w;}eg[MAXM];int head[MAXN];int cnt=0;int s,t;int dist[MAXN];bool canUse[MAXN];bool vis[MAXN];void add(int a,int b,int w){    cnt++;    eg[cnt].to=b;    eg[cnt].next=head[a];    eg[cnt].w=w;    head[a]=cnt;}void spfa(int st){    memset(dist,0x7f,sizeof(dist));    memset(vis,false,sizeof(vis));        queue
        
          q;    if(canUse[st]){        q.push(st);        dist[st]=0;        vis[st]=true;    }        while(!q.empty()){        int k=q.front(); q.pop();        vis[k]=false;        for(int i=head[k];i!=-1;i=eg[i].next){            int u=eg[i].to;            if(canUse[u]){                if(dist[u]>dist[k]+eg[i].w){                    dist[u]=dist[k]+eg[i].w;                    if(!vis[u]){                        vis[u]=true;                        q.push(u);                    }                }            }        }    }}int main(){    memset(canUse,true,sizeof(canUse));    memset(head,-1,sizeof(head));        cin>>n>>m;    int a,b,w;    for(int i=1;i<=m;i++){        cin>>a>>b;        add(b,a,1);    }    cin>>s>>t;    spfa(t);    for(int i=1;i<=n;i++){        if(dist[i]>=INF){            //cout<<"Can't Use:"<
         <
          
           =INF)cout<<-1<