洛谷 2296_寻找道路_spfa+dfs

2019-11-06 06:28:42

字体：大中小

来源：转载

供稿：网友

题目描述

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

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

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

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

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

思路

题目的意思是最短路上的点的所有出度都必须可以走到终点

首先从终点进行一次dfs，标记出那些点可以走到，然后spfa一下，每走一个点都暴力枚举全部出度，判断一下就可以了

#include <stdio.h>#include <queue>#include <iostream>#define maxn 200001#define INF 2147483647using namespace std;int l=0,s;struct arr { int x,y,w,next; };int x,y,z,e;arr edge[maxn],edge1[maxn];int ls[maxn],ls1[maxn];int state[maxn];bool exits[maxn];int f[maxn],c[maxn],fl[maxn];int dfs(int x){ if (x==0) return 0; int i=ls1[x]; while (i!=0) { if(fl[edge1[i].y]==0) { f[edge1[i].y]=1; fl[edge1[i].y]=1; dfs(edge1[i].y); } i=edge1[i].next; } return 0;}int spfa(){ int i; queue <int> t; t.push(s); state[s]=0; exits[s]=true; do { int tt=t.front(); t.pop(); i=ls[tt]; int j=ls[tt],ff=1; while (j!=0) { if (f[edge[j].y]==0) ff=0; j=edge[j].next; } while (i!=0&&ff==1) { if (state[edge[i].x]+edge[i].w<state[edge[i].y]&&f[edge[i].y]>0&&f[edge[i].x]>0) { state[edge[i].y]=state[edge[i].x]+edge[i].w; if (exits[edge[i].y]==false) { t.push(edge[i].y); exits[edge[i].y]=true; } } i=edge[i].next; } exits[tt]=false; } while (!t.empty());}int main(){ int j,k,n,m; scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); edge[++l]=(arr){x,y,1,ls[x]}; edge1[l]=(arr){y,x,1,ls1[y]}; c[x]++; ls[x]=l; ls1[y]=l; } for (int i=1;i<maxn;i++) state[i]=INF; scanf("%d%d",&s,&e); fl[e]=1; f[e]=1; dfs(e); spfa(); if (state[e]==INF) state[e]=-1; PRintf("%d/n",state[e]);}

上一篇：字符串的（暴力）枚举连续子串2

下一篇：多线程_多线程程序的引入

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注