题目描述

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

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

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

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

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

输入输出格式

输入格式：

输入文件名为road .in。

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

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

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

输出格式：

输出文件名为road .out 。

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

输入输出样例

3 2  1 2  2 1  1 3  

-1

6 6  1 2  1 3  2 6  2 5  4 5  3 4  1 5  

3

说明

解释1：

如上图所示，箭头表示有向道路，圆点表示城市。起点1 与终点3 不连通，所以满足题

目?述的路径不存在，故输出- 1 。

解释2：

如上图所示，满足条件的路径为1 - >3- >4- >5。注意点2 不能在答案路径中，因为点2连了一条边到点6 ，而点6 不与终点5 连通。

对于30%的数据，0<n≤10，0<m≤20；

对于60%的数据，0<n≤100，0<m≤2000；

对于100%的数据，0<n≤10,000，0<m≤200,000，0<x，y，s，t≤n，x≠t。

代码

 1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #define MAXN 500005 8 #define INF 0x3f3f3f3f 9 using namespace std;10 11 int vis[MAXN],to_des[MAXN],dis[MAXN];12 int N,M;13 int s,t;14 15 struct cc{int d,num;};16 struct cmp{bool operator()(cc a,cc b){return a.d>b.d;}};17 cc make_(int d,int num){cc a;a.d=d;a.num=num;return a;}18 19 vector<int> rG[MAXN],G[MAXN];20 21 void Dijkstra(){22     priority_queue<cc,vector<cc>,cmp> q;23     memset(dis,0x3f,sizeof(dis));24     memset(vis,0,sizeof(vis));25     26     q.push(make_(0,s));27     dis[s]=0;28     29     while(!q.empty()){30         cc x=q.top();q.pop();31         vis[x.num]=1;32         33         int flag=0;34         for(int i=0;i<G[x.num].size();i++){35             int to=G[x.num][i];36             if(!to_des[to]) {flag=1;break;}37         }38         if(flag) continue;39         40         for(int i=0;i<G[x.num].size();i++){41             int to=G[x.num][i];42             if(dis[x.num]+1<dis[to]){43                 dis[to]=dis[x.num]+1;44                 q.push(make_(dis[to],to));45             }46         }47     }48 }49 50 void rdfs(int x){51     vis[x]=to_des[x]=1;52     for(int i=0;i<rG[x].size();i++){53         int to=rG[x][i];54         if(!vis[to]) rdfs(to);55     }56 }57 58 void init_(){59     scanf("%d%d",&N,&M);60     for(int i=1;i<=M;i++){61         int from,to;62         scanf("%d%d",&from,&to);63         G[from].push_back(to);64         rG[to].push_back(from);65     }66     scanf("%d%d",&s,&t);67     rdfs(t);68 }69 70 int main(){71     freopen("road.in","r",stdin);72     freopen("road.out","w",stdout);73     74     init_();75     Dijkstra();76 77     if(dis[t]==INF) puts("-1");78     else printf("%d\n",dis[t]);79     80     return 0;81 }

90分 TLE

 

转载：

首先把路线全倒过来，从终点往起点走一遍，把不行的点标起来，然后再从起点往终点做一个bfs，求最短的路线，就行了

 1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<vector> 7 using namespace std; 8 int x,y,s,t,n,m,h[10002],f[10002],tr; 9 vector<int>a[10002],b[10002];10 void dfs(int u){11     if (h[u])return;12     f[u]=1;h[u]=1;13     for (int i=0;i<b[u].size();i++)14     dfs(b[u][i]);15 }16 void bfs(int u){17     int g[10002],ans[10002],l=0,fl[10002],xx;18     memset(fl,0,sizeof(fl));memset(ans,0,sizeof(ans));19     for (int i=0;i<a[u].size();i++)20     if (!fl[a[u][i]] && f[a[u][i]])21     {ans[l]=1;g[l++]=a[u][i];fl[a[u][i]]=1;}22     for (int i=0;i<l;i++)23     {24         if (g[i]==t){tr=1;printf("%d",ans[i]);break;}25         xx=g[i];26         for (int j=0;j<a[xx].size();j++)27         if (!fl[a[xx][j]] && f[a[xx][j]])28         {ans[l]=ans[i]+1;g[l++]=a[xx][j];fl[a[xx][j]]=1;}29     }30 }31 int main()32 {33     scanf("%d%d",&n,&m);34     for (int i=0;i<m;i++)35     {36         scanf("%d%d",&x,&y);37         a[x].push_back(y);b[y].push_back(x);38     }39     scanf("%d%d",&s,&t);40     dfs(t);41     memset(h,0,sizeof(h));42     for (int i=1;i<=n;i++)43     {44         if (!f[i])continue;45         for (int j=0;j<a[i].size();j++)46         if (!f[a[i][j]]){h[i]=1;break;}47     }48     for (int i=1;i<=n;i++)49     if (h[i])f[i]=0;50     if (f[s])bfs(s);51     if (!tr)printf("-1");52     return 0;53 }

std

 

NOIp 2014 #3 寻找道路 Label:图论