NOIp 2014 寻找道路【图的遍历/最短路】By cellur925

比较裸的图论，结果自己还是没做出来，我真菜。

我们根据题意，只要把不能通向终点的点求出，然后再分别以这些点为起点，求出它们能到达的点，这些点也不能在路径上。

之后跑一个最短路即可。

注意以上操作均是在建反图的基础上进行的。我们交换起终点，这是等价的。

细节操作：开新数组记录不能到达的点，因为搜索还没结束，会重复。

Code

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int inf=0x3f3f3f3f;

 int n,m,x,y,s,t,tot,qwq;

 int head[],vis[],laz1[],dis[],tmp[],laz[];

 struct node{

     int to,next;

 }edge[];

 void add(int x,int y)

 {

     edge[++tot].to=y;

     edge[tot].next=head[x];

     head[x]=tot;

 }

 void dfs(int x)

 {

     laz1[x]=;

     for(int i=head[x];i;i=edge[i].next)

     {

         int y=edge[i].to;

         if(laz1[y]) continue;

         dfs(y);

     }

 }

 void spfa()

 {

     queue<int>q;

     for(int i=;i<=n;i++) dis[i]=inf;

     q.push(t);vis[t]=;dis[t]=;

     while(!q.empty())

     {

         int x=q.front();q.pop();vis[x]=;

         if(!laz[x]) continue;

         for(int i=head[x];i;i=edge[i].next)

         {

             int y=edge[i].to;

             if(dis[y]>dis[x]+&&laz[y])

             {

                 dis[y]=dis[x]+;

                 if(!vis[y]) q.push(y),vis[y]=;

             }

         }

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)

         scanf("%d%d",&x,&y),add(y,x);

     scanf("%d%d",&s,&t);

     dfs(t);

     if(!laz1[s])

     {

         printf("-1");

         return ;

     }

     for(int i=;i<=n;i++)

     {

         if(!laz1[i])

         {

             for(int k=head[i];k;k=edge[k].next)

                 tmp[++qwq]=edge[k].to;

         }

         else laz[i]=;

     }

     for(int i=;i<=qwq;i++) laz[tmp[i]]=;

     spfa();

     printf("%d",dis[s]);

     return ;

 }

巴特西

NOIp 2014 寻找道路【图的遍历/最短路】By cellur925

最新文章

热门文章