10.22T6 水题-白红宇

10.22T6 水题

阅读量：6583 次

发布时间：2019-06-24

本文共 2465 字，大约阅读时间需要 8 分钟。

Description

　　在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：

　　1．路径上的所有点的出边所指向的点都直接或间接与终点连通。

　　2．在满足条件1的情况下使路径最短。

　　注意：图G中可能存在重边和自环，题目保证终点没有出边。

　　请你输出符合条件的路径的长度。

Input

　　输入文件名为road .in。

　　第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。

　　接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。

　　最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t。

Output

　　输出文件名为road .out 。

　　输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出- 1。

Sample Input

3 2 1 2 2 1 1 3

Sample Output

-1

Hint

road.in

6 6

1 2

1 3

2 6

2 5

4 5

3 4

1 5

road.out

反向跑一次记录不能到达的点，然后记录与之相连的点，正向跑一边spfa

code:

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define N 1000005 6 using namespace std; 7 struct node{ 8     int u,v; 9 }e[N],e1[N];10 int s,t,first[N],nxt[N],cnt;11 void add(int u,int v){12     e[++cnt].u=u;13     e[cnt].v=v;14     nxt[cnt]=first[u];15     first[u]=cnt;16 }17 int first1[N],nxt1[N],cnt1;18 void add1(int u,int v){19     e1[++cnt1].u=u;20     e1[cnt1].v=v;21     nxt1[cnt1]=first1[u];22     first1[u]=cnt1;23 }24 int vis[N],dis[N],visit[N];25 void dfs(int x){26     visit[x]=1;27     for(int i=first[x];i;i=nxt[i]){28         int v=e[i].v;29         if(visit[v])continue;30         dfs(v);31     }32 }33 int check[N];34 void spfa(){35     queue
          
           q;36     memset(dis,0x3f3f3f3f,sizeof dis);37     memset(vis,0,sizeof vis);38     vis[s]=1;39     dis[s]=0;40     q.push(s);41     while(!q.empty()){42         int u=q.front();43         q.pop();44         vis[u]=0;45     //    cout<
           <<":from"<<'\n';46 for(int i=first1[u];i;i=nxt1[i]){47 int v=e1[i].v;48 // cout<
            
             <<":to"<<'\n';49 if(check[v])continue;50 if(dis[v]>dis[u]+1){51 dis[v]=dis[u]+1;52 if(!vis[v]){53 vis[v]=1;54 q.push(v);55 }56 }57 }58 }59 }60 long long read(){61 long long x=0,f=1;62 char c=getchar();63 while(!isdigit(c)){64 if(c=='-')f=-1;65 c=getchar();66 }67 while(isdigit(c)){68 x=(x<<3)+(x<<1)+c-'0';69 c=getchar();70 }71 return x*f;72 }73 int main(){74 int n,m;75 n=read(),m=read();76 for(int i=1;i<=m;i++){77 int u,v;78 u=read(),v=read();79 add(v,u);80 add1(u,v);81 }82 s=read(),t=read();83 dfs(t);84 for(int i=1;i<=n;i++){85 if(visit[i])continue;86 check[i]=1;87 for(int j=first[i];j;j=nxt[j]){88 int v=e[j].v;89 check[v]=1;90 }91 }92 // for(int i=1;i<=n;i++)cout<
             
              <<'\n';93 spfa();94 cout<<(dis[t]==0x3f3f3f3f?-1:dis[t]);95 return 0;96 }