洛谷 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;