题解 - Vijos

7

ATHENS_ LV 9 @ 2017-10-15 11:54:41

两遍spfa，第一遍反向看有哪些点不联通，标记上，第二次正向spfa，标记了的点不能用来更新。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=1e4+5;
const int MAXN=2e5+5;
const int inf=0x3f3f3f3f;
int n,m,cnt,x[MAXN],y[MAXN],s,t,head[maxn],dis[maxn];
bool vis[maxn],judge[maxn];
struct edge{
    int v,nxt;
}d[MAXN];
queue <int> q;
inline void add(int a,int b){
    d[++cnt].v=b;d[cnt].nxt=head[a];head[a]=cnt;
}

void spfa(int st){
    memset(vis,0,sizeof vis);
    memset(dis,63,sizeof dis);
    dis[st]=0;
    q.push(st);vis[st]=1;
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=1;
        for(int i=head[u];i;i=d[i].nxt){
            int v=d[i].v;
            if(judge[v])continue;
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x[i],&y[i]);
        add(y[i],x[i]);
    }
    scanf("%d%d",&s,&t);
    spfa(t);
    if(dis[s]==inf){
        printf("-1");
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(dis[i]==inf){
            for(int j=head[i];j;j=d[j].nxt){
                judge[d[j].v]=1;
            }
        }
    }
    if(judge[s]==1){
        printf("-1");
        return 0;
    }
    cnt=0;memset(head,0,sizeof head);
    for(int i=1;i<=m;i++){
        add(x[i],y[i]);
    }
    spfa(s);
    if(dis[t]<=inf)printf("%d",dis[t]);
    else printf("-1");
    
    
    return 0;
}

2

orangebird LV 8 @ 2016-10-22 18:44:14

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
using namespace std;
int n,m,s,t;
vector<int>anti_cn[10010],cn[10010];
queue<int> q;
int dis[10010];
bool unable[10010];
void bfs(int x)
{
    memset(dis,-1,sizeof(dis));
    q.push(x);
    dis[x]=0;
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        for(int i=0;i<anti_cn[now].size();++i)
        {
            int nex = anti_cn[now][i];
            if(dis[nex]!=-1||unable[nex])continue;
            dis[nex]=dis[now]+1;
            q.push(nex);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        cn[x].push_back(y);
        anti_cn[y].push_back(x);
    }
    scanf("%d%d",&s,&t);
    bfs(t);
    for(int i=1;i<=n;++i)
        for(int j=0;j<cn[i].size();++j)
            if(dis[cn[i][j]]==-1)
            {
               unable[i]=1;
               break;
            }
    bfs(t);
    cout<<dis[s]<<endl;
    return 0;
}

1

Lifi LV 10 @ 2019-08-01 14:47:05

改了2小时，都改吐了。
说一下思路吧：
1.从终点开始DFS，查找到底哪些点能够到达终点，标记出与终点联通的点。这些点的入边的另一个端点都是不符合题目要求的。
2.遍历第一步中标记出的点的入边，将入边的两个端点都标记为不可用。
3.从起点开始BFS，不可用的点直接跳过，不进入队列。
最开始用的邻接矩阵，最后一个点死活过不去，但是代码好理解一些，我也贴出来吧：

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

typedef struct
{
    int x,d;
}po;

int n;
bool edge[10001][10001]={0};
int from,to;
bool vis[10001]={0};
bool reach[10001]={0};
bool bfsv[10001]={0};
queue<po> que;

void vdfs(int x)
{
    vis[x]=true;
    reach[x]=true;
    int i;
    for(i=1;i<=n;i++)
    {
        if(edge[i][x]&&!vis[i])
        {
            vdfs(i);
        }
    }
}

int main()
{
    int m,i,j,k;
    cin>>n>>m;
    for(i=0;i<m;i++)
    {
        //cin>>j>>k;
        scanf("%d%d",&j,&k);
        edge[j][k]=true;
    }
    cin>>from>>to;
    vdfs(to);
    if(!vis[from])
    {
        cout<<-1<<endl;
        return 0;
    }
    for(i=1;i<=n;i++)
    {
        if(reach[i])
        {
            for(j=1;j<=n;j++)
            {
                if(edge[i][j]&&!vis[j])//存在出边但出边点不可达
                {
                    reach[i]=false;
                    break;
                }
            }
        }
    }
    po push,now;
    push.x=from;
    push.d=0;
    que.push(push);
    while(!que.empty())
    {
        now=que.front();
        que.pop();
        bfsv[now.x]=true;
        if(now.x==to)
        {
            cout<<now.d<<endl;
            return 0;
        }
        else
        {
            for(i=1;i<=n;i++)
            {
                if(edge[now.x][i]&&reach[i]&&!bfsv[i])
                {
                    push.x=i;
                    push.d=now.d+1;
                    que.push(push);
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

最后改用vector做邻接表，终于过了：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef struct
{
    int x,d;
}po;

int n;
vector<int> cu[10001],ru[10001];
int from,to;
bool vis[10001]={0};
bool reach[10001]={0};
bool bfsv[10001]={0};
queue<po> que;

void vdfs(int x)
{
    vis[x]=true;
    reach[x]=true;
    int i;
    for(i=ru[x].size()-1;i>=0;i--)
    {
        if(!vis[ru[x][i]])
        {
            vdfs(ru[x][i]);
        }
    }
}

int main()
{
    int m,i,j,k;
    cin>>n>>m;
    for(i=0;i<m;i++)
    {
        cin>>j>>k;
        cu[j].push_back(k);
        ru[k].push_back(j);
    }
    cin>>from>>to;
    vdfs(to);
    if(!vis[from])
    {
        cout<<-1<<endl;
        return 0;
    }
    for(i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            for(j=ru[i].size()-1;j>=0;j--)
            {
                reach[ru[i][j]]=false;
            }
        }
    }
    po push,now;
    push.x=from;
    push.d=0;
    que.push(push);
    while(!que.empty())
    {
        now=que.front();
        que.pop();
        bfsv[now.x]=true;
        if(now.x==to)
        {
            cout<<now.d<<endl;
            return 0;
        }
        else
        {
            for(i=cu[now.x].size()-1;i>=0;i--)
            {
                if(reach[cu[now.x][i]]&&!bfsv[cu[now.x][i]])
                {
                    push.x=cu[now.x][i];
                    push.d=now.d+1;
                    que.push(push);
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}

1

passer_1 LV 9 @ 2017-10-14 23:38:51

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#define Clear(x,y) memset(x,y,sizeof x)
using namespace std;
const int MAXN=100033;
const int INF=0x3f3f3f3f;
struct Edge
{
    int nx,to;
}E[MAXN<<2],E_[MAXN<<2];
int first[MAXN],first_[MAXN],ecnt=1;
inline void addedge(int f,int t)
{
    ++ecnt;
    E [ecnt]=(Edge){first [f],t};first [f]=ecnt;
    E_[ecnt]=(Edge){first_[t],f};first_[t]=ecnt;
}
int n,m,S,T;
int dist_[MAXN],dist[MAXN];
bool in_[MAXN],in[MAXN];
queue<int> Q;
bool ok[MAXN];
inline void spfa(bool ok[],int dist[],int first[],bool in[],Edge E[],int S,int T)
{
    while(!Q.empty()) Q.pop();
    int e,r;
    Q.push(S);
    dist[S]=0;
    while(!Q.empty())
    {
        e=Q.front();Q.pop();
        in[e]=0;
        for(int i=first[e];i;i=E[i].nx)
        {
            if(ok[(r=E[i].to)]&&dist[r]>dist[e]+1)
            {
                dist[r]=dist[e]+1;
                if(!in[r]){
                    in[r]=1;
                    Q.push(r);
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        addedge(x,y);
    }
    scanf("%d%d",&S,&T);
    Clear(dist,63);
    Clear(dist_,63);
    Clear(ok,true);
    spfa(ok,dist_,first_,in_,E_,T,S);
    Clear(ok,false);
    for(int i=1;i<=n;++i)
    {
        bool flag=1;
        for(int j=first[i];j;j=E[j].nx)
            if(dist_[E[j].to]==INF) flag=0;
        ok[i]=flag;
    }
    spfa(ok,dist,first,in,E,S,T);
    if(dist[T]<INF)
        printf("%d",dist[T]);
    else
        printf("-1");
    return 0;
}

1

Pia LV 9 @ 2016-09-24 20:25:02

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn =  10000 + 50;
const int INF = 1000000000;

int n, m, s, t, to[maxn], ok[maxn], dist[maxn], inque[maxn];
vector<int> g[maxn];
vector<int> g1[maxn];
queue<int> q;
void init(){
    cin >> n >> m;
    int x, y;
    for(int i = 0; i < m; i++){
        cin >> x >> y; x--; y--;
        //if(x == 0) cout << y << endl;
        g[x].push_back(y);
        g1[y].push_back(x);
    }
    cin >> s >> t;
    s--; t--;
}
void dfs(int k){
    if(to[k]) return;
    to[k] = 1;
    for(int i = 0; i < g1[k].size(); i++) dfs(g1[k][i]);
}
void spfa(){
    dist[s] = 0;
    q.push(s); inque[s] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop(); inque[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
                if(ok[u] && dist[u] + 1 < dist[v]){
                    dist[v] = dist[u] + 1;
                    q.push(v); inque[v] = 1;
                }
        }
    }
}
void work(){
    dfs(t); //计算哪些点可以到达终点
    for(int i = 0; i < n; i++){
        dist[i] = INF;
        ok[i] = 1;
        for(int j = 0; j < g[i].size(); j++){
            if(!to[g[i][j]]) ok[i] = 0;
        }
    }
    spfa();
    if(dist[t] < INF)
        cout << dist[t] <<endl;
    else
        cout << -1;
}
int main(){
    //freopen ( "in.txt" , "r" , stdin);
    init();
    work();
    
    return 0;
}

1

Rachelselfish LV 8 @ 2015-07-16 16:33:26

建两个图，一个正图一个反图，两次SPFA。先遍历反图找到dis=inf的点，把和他相连的点都标记，第二次SPFA的时候不用他。第二次正向SPFA，直接找最短路输出就可以了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#define maxx 300000
using namespace std;

int n,m,x,y,s,t,size,Size;
int first[maxx],dis[maxx],p[maxx],First[maxx],Dis[maxx],P[maxx];
bool judge[maxx],jud[maxx];

struct node
{
int to;
int next;
int len;
}edge[maxx],Edge[maxx];

void insert(int x,int y,int z)
{
size++;
edge[size].to=y;
edge[size].next=first[x];
edge[size].len=z;
first[x]=size;
}

void Insert(int x,int y,int z)
{
Size++;
Edge[Size].to=y;
Edge[Size].next=First[x];
Edge[Size].len=z;
First[x]=Size;
}

void Spfa(int t)
{
fill(Dis,Dis+1+n,1000000);
int head=0;
int tail=1;
P[tail]=t;
Dis[t]=0;
judge[t]=true;
while(head<tail)
{
head++;
judge[P[head]]=true;
for(int i=First[P[head]];i!=0;i=Edge[i].next)
{
int k=Edge[i].to;
if(Dis[P[head]]+Edge[i].len<Dis[k])
{
Dis[k]=Dis[P[head]]+Edge[i].len;
if(judge[k]==false)
{
judge[k]=true;
tail++;
P[tail]=k;
}
}
}
}
}

void spfa(int t)
{
memset(judge,false,sizeof(judge));
fill(dis,dis+n+1,1000000);
int head=0;
int tail=1;
dis[t]=0;
p[tail]=t;
judge[t]=true;
while(head<tail)
{
head++;
judge[p[head]]=true;
for(int i=first[p[head]];i!=0;i=edge[i].next)
{
int k=edge[i].to;
if(dis[p[head]]+edge[i].len<dis[k]&&jud[k]==true)
{
dis[k]=dis[p[head]]+edge[i].len;
if(judge[k]==false)
{
judge[k]=true;
tail++;
p[tail]=k;
}
}
}
}
}

int main()
{
freopen("find.in","r",stdin);
freopen("find.out","w",stdout);

memset(jud,true,sizeof(jud));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
insert(x,y,1);
Insert(y,x,1);
}
scanf("%d%d",&s,&t);
Spfa(t);
for(int i=1;i<=n;i++)
if(Dis[i]==1000000)
for(int j=First[i];j!=0;j=Edge[j].next)
{
int k=Edge[j].to;
jud[k]=false;
}
spfa(s);
if(dis[t]==1000000)
{
printf("-1");
return 0;
}
else
printf("%d",dis[t]);
}

0

SHZhang LV 8 @ 2018-08-13 10:22:31

先找出所有不能经过的点，然后SPFA。

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

int n, m, s, t;

vector<int> conn[10001];
vector<int> rev_conn[10001];

bool marked[10001];
bool OK[10001];

int dist[10001];

void mark_as_conn(int node)
{
    marked[node] = true;
    for (int i = 0; i < rev_conn[node].size(); i++) {
        int x = rev_conn[node][i];
        if (!marked[x]) {
            mark_as_conn(x);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        conn[x].push_back(y);
        rev_conn[y].push_back(x);
    }
    
    scanf("%d%d", &s, &t);
    mark_as_conn(t);
    
    for (int i = 1; i <= n; i++) {
        dist[i] = 2000000000;
        OK[i] = true;
        for (int j = 0; j < conn[i].size(); j++) {
            if (!marked[conn[i][j]]) OK[i] = false;
        }
    }
    
    if (!OK[s]) {
        printf("-1\n");
        return 0;
    }
    
    dist[s] = 0;
    
    queue<int> que;
    que.push(s);
    
    while (!que.empty()) {
        int elem = que.front();
        que.pop();
        for (int i = 0; i < conn[elem].size(); i++) {
            if (OK[conn[elem][i]] && dist[elem] + 1 < dist[conn[elem][i]]) {
                dist[conn[elem][i]] = dist[elem] + 1;
                que.push(conn[elem][i]);
            }
        }
    }
    
    if (dist[t] == 2000000000) {
        printf("-1\n");
    } else {
        printf("%d", dist[t]);
    }
    
    return 0;
}

0

hanghang0702 LV 8 @ 2017-11-04 13:46:48

楼下的！为什么要spfa？bfs就够了。。。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define M 205555
#define N 20005
#define MAKECOLOR
#define WHITE 0x0
#define INF 2100000000
#define GRAY 0x1
#define BLACK 0x2
#define FAILED {puts("-1");return 0;}
int n,m,s,t,ans=2100000000;
int flag[N];
int color[N];
struct edge_t{int to,next;};
struct edges_t{
    edge_t edg[M];
    int head[N];
    int num;
    edges_t(){for (int i=1;i<N;i++) head[i]=-1;}
} edges, sedge;


void Addedge(edges_t& edges, int x,int y){
    edges.edg[edges.num] = (edge_t){y, edges.head[x]};
    edges.head[x] = edges.num++;
}
void dfs(int u){
    color[u] = MAKECOLOR GRAY;
    for(int e=sedge.head[u]; e!=-1; e=sedge.edg[e].next){
        int v=sedge.edg[e].to;
        if(color[v] == MAKECOLOR WHITE) {
            dfs(v);
        }
    }
    color[u] = MAKECOLOR BLACK;
}

#include<queue>
queue<int> Q; int dis[N];

int dfsans(int u,int depth){
    for(int i=1;i<=n;i++)dis[i]=INF;
    dis[s] = depth;
    Q.push(s);
    while(!Q.empty()){
        int u=Q.front();Q.pop();
        for(int e=edges.head[u]; e!=-1; e=edges.edg[e].next){
            int v=edges.edg[e].to;
            if(!flag[v] && dis[v]==INF){
                if(v==t) return dis[u]+1;
                dis[v]=dis[u]+1;
                Q.push(v);
            }
        }
    }
    return -1;
}
int main(){
    scanf("%d%d", &n,&m); int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d", &x,&y);
        Addedge(edges, x,y);
        Addedge(sedge, y,x);
    }
    scanf("%d%d", &s,&t);
    dfs(t);
    for(int i=1;i<=n;i++){
        if(color[i] == MAKECOLOR WHITE){
            flag[i]=1;
            for(int e=sedge.head[i]; e!=-1; e=sedge.edg[e].next){
                int v=sedge.edg[e].to;
                flag[v]=1;
            }
        }
    }
    if(flag[s]) FAILED;
    for(int i=1;i<=n;i++)color[i]=MAKECOLOR WHITE;
    printf("%d\n", dfsans(s,0));
    return 0;
}

0

hanghang0702 LV 8 @ 2017-11-04 13:45:17

反向边，dfs判断无法到达的点
然后bfs最短路

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define M 205555
#define N 20005
#define MAKECOLOR
#define WHITE 0x0
#define INF 2100000000
#define GRAY 0x1
#define BLACK 0x2
#define FAILED {puts("-1");return 0;}
int n,m,s,t,ans=2100000000;
int flag[N];
int color[N];
struct edge_t{int to,next;};
struct edges_t{
    edge_t edg[M];
    int head[N];
    int num;
    edges_t(){for (int i=1;i<N;i++) head[i]=-1;}
} edges, sedge;


void Addedge(edges_t& edges, int x,int y){
    edges.edg[edges.num] = (edge_t){y, edges.head[x]};
    edges.head[x] = edges.num++;
}
void dfs(int u){
    color[u] = MAKECOLOR GRAY;
    for(int e=sedge.head[u]; e!=-1; e=sedge.edg[e].next){
        int v=sedge.edg[e].to;
        if(color[v] == MAKECOLOR WHITE) {
            dfs(v);
        }
    }
    color[u] = MAKECOLOR BLACK;
}

#include<queue>
queue<int> Q; int dis[N];

int dfsans(int u,int depth){
    for(int i=1;i<=n;i++)dis[i]=INF;
    dis[s] = depth;
    Q.push(s);
    while(!Q.empty()){
        int u=Q.front();Q.pop();
        for(int e=edges.head[u]; e!=-1; e=edges.edg[e].next){
            int v=edges.edg[e].to;
            if(!flag[v] && dis[v]==INF){
                if(v==t) return dis[u]+1;
                dis[v]=dis[u]+1;
                Q.push(v);
            }
        }
    }
    return -1;
}
int main(){
    scanf("%d%d", &n,&m); int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d", &x,&y);
        Addedge(edges, x,y);
        Addedge(sedge, y,x);
    }
    scanf("%d%d", &s,&t);
    dfs(t);
    for(int i=1;i<=n;i++){
        if(color[i] == MAKECOLOR WHITE){
            flag[i]=1;
            for(int e=sedge.head[i]; e!=-1; e=sedge.edg[e].next){
                int v=sedge.edg[e].to;
                flag[v]=1;
            }
        }
    }
    if(flag[s]) FAILED;
    for(int i=1;i<=n;i++)color[i]=MAKECOLOR WHITE;
    printf("%d\n", dfsans(s,0));
    return 0;
}

0

Antinomy LV 8 @ 2017-02-14 16:25:47

不知道是不是数据出问题了，很多题解最后一个点都Tle我的也是。。然后我发现必须要把在spfa中判断是不是到达终点并且一到终点就结束spfa

0

Onlynagesha LV 9 @ 2017-01-30 11:27:46

首先逆向bfs一遍，确定每个点是否满足题中的条件1，然后正向bfs求最短路径
#include <algorithm>
#include <utility>
#include <bitset>
#include <cctype>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define irep(i,a,b) for(int i=(a);i>(b);i--)
#define reset(a,c) memset(a,c,sizeof(a))

typedef long long int64;

const int inf = 0x3f3f3f3f;

const int maxN = 10000 + 5;
const int maxM = 200000 + 5;

struct Edge
{
int to, next;
void assign (int t, int n)
{
to = t, next = n;
}
};

Edge elist[maxM], ielist[maxM];
int head[maxN], ihead[maxN];
int ecnt (0);

void add (int f, int t)
{
elist[ecnt].assign (t, head[f]);
ielist[ecnt].assign (f, ihead[t]);
head[f] = ecnt;
ihead[t] = (ecnt++);
}

int N, M;
int S, T;

void input()
{
reset (head, -1), reset (ihead, -1);
scanf ("%d%d", &N, &M);
int x, y;
rep (i, 0, M)
{
scanf ("%d%d", &x, &y);
add (x, y);
}
scanf ("%d%d", &S, &T);
}

bool vis[maxN] = {0};
bool av[maxN] = {0};

void bfs1()
{
queue<int> que;
que.push (T);
vis[T] = true;
while (!que.empty() )
{
int cur = que.front();
que.pop();
int t;
for (int e = ihead[cur]; e != -1; e = ielist[e].next)
{
t = ielist[e].to;
if (!vis[t])
{
vis[t] = true;
que.push (t);
}
}
}
rep (i, 1, N + 1)
{
av[i] = true;
int t;
for (int e = head[i]; e != -1; e = elist[e].next)
{
t = elist[e].to;
if (!vis[t])
{
av[i] = false;
break;
}
}
}
}

int dist[maxN];

int bfs2()
{
reset (dist, 0x3f);
queue<int> que;
que.push (S);
dist[S] = 0;
while (!que.empty() )
{
int cur = que.front();
que.pop();
int t;
for (int e = head[cur]; e != -1; e = elist[e].next)
{
t = elist[e].to;
if (dist[t] > dist[cur] + 1 && av[t])
{
dist[t] = dist[cur] + 1;
if (t == T) return dist[t];
que.push (t);
}
}
}
return dist[T] == inf ? -1 : dist[T];
}

int main()
{
input();
bfs1();
printf ("%d\n", bfs2() );
return 0;
}

Antinomy @ 2017-02-14 16:30:02

请问
if (t == T) return dist[t];
为何只要spfa到终点就输出。。而且似乎不这样就会最后一个点tle

0

linhui LV 9 @ 2016-11-18 13:41:17

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int M = 10005;
typedef pair<int, int> pir;
#define fs first
#define se second

int n, m, s, t;
int vis[M], no[M];
vector<int> map[M], tu[M];

void BFS(){
queue<int> Q;
Q.push(t);
vis[t] = 1;
while(!Q.empty()){
int now = Q.front();
Q.pop();

for(int i = 0; i < tu[now].size(); i++){

int e = tu[now][i];
if(vis[e]) continue;
vis[e] = 1;
Q.push(e);
}
}
}

int BFS2(){
if(no[s]) return -1;
queue<pir> Q;
Q.push(make_pair(s, 0));
while(!Q.empty()){
pir now = Q.front();
Q.pop();

if(now.fs == t) return now.se;
for(int i = 0; i < map[now.fs].size(); i++){

int e = map[now.fs][i];
if(no[e] || vis[e]) continue;
vis[e] = 1;
Q.push(make_pair(e, now.se + 1));
}
}
return -1;
}

int main()
{
freopen("in", "r", stdin);
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++){
int x, y;
scanf("%d%d", &x, &y);
map[x].push_back(y);
tu[y].push_back(x);
}
scanf("%d%d", &s, &t);
BFS();
for(int i = 1; i <= n; i++)
if(!vis[i]){
no[i] = 1;
for(int j = 0; j < tu[i].size(); j++)
no[tu[i][j]] = 1;
}
memset(vis, 0, sizeof(vis));
printf("%d", BFS2());
return 0;
}

0

205610760 LV 8 @ 2016-11-17 20:26:49

canVis[top]写成了canVis[to]。。。于是MLE了。。
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int n,m,_start,_end;
int vis[10010],inq[10010],canVis[10010],vis2[10010],d[10010];

vector<int>G1[10010],G2[10010];

queue<int>q;

void add(int u,int v){
G1[u].push_back(v);
G2[v].push_back(u);
}

void dfs(int x){
if(vis[x])return;
vis[x]=1;
for(int i=0;i<G2[x].size();i++)
dfs(G2[x][i]);
}

void SPFA(){
inq[_start]=1;
q.push(_start);
memset(d,0x3f,sizeof(d));
d[_start]=0;
while(q.size()){
int top=q.front();q.pop();inq[top]=0;
if(canVis[top])
for(int i=0,to;i<G1[top].size();i++)
if(to=G1[top][i],d[to]>d[top]+1)
if((d[to]=d[top]+1),!inq[to])
inq[to]=1,q.push(to);
}
printf("%d\n",d[_end]==0x3f3f3f3f?-1:d[_end]);
}

int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
scanf("%d%d",&_start,&_end);
dfs(_end);

for(int i=1;i<=n;i++)
{
canVis[i]=1;
for(int j=0;j<G1[i].size();j++){
if(!vis[G1[i][j]]){
canVis[i]=0;
}
}
}
SPFA();
}

0

lolix LV 7 @ 2016-11-14 20:28:47

建立正向图与反向图
反向图终点开始dfs 记录可以到达终点的点
正向图依次访问每个的点的出边的点，
看看能不能到达终点并标记每个点
最后SPFA 只走符合要求的点
#include <cstdio>
#include <queue>

struct edge{
int v,val;
edge *link;
};

int n,m,START,END,top=0;
edge graph[11000]={0};
edge g2[11000]={0};
edge node[410000];

void add(int u,int v,int val){
edge *l=&node[top++];
l->v=v,l->val=val;
l->link=graph[u].link;
graph[u].link=l;
}

void add2(int u,int v,int val){
edge *l=&node[top++];
l->v=v,l->val=val;
l->link=g2[u].link;
g2[u].link=l;
}

void build(){
scanf("%d%d",&n,&m);
int u,v;
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v,1);
add2(v,u,1);

}
scanf("%d%d",&START,&END);
}

//DFS
int vis[11000]={0};
void dfs(int u){
vis[u]=1;
edge *l=g2[u].link;
while(l){
if(!vis[l->v])
dfs(l->v);
l=l->link;
}
}

//SPFA
std::queue<int> q;
int inque[11000]={0};
int dist[11000];

void spfa(int u){
dist[u]=0;
q.push(u),inque[u]=1;
while(!q.empty()){
int t=q.front();
q.pop(),inque[t]=0;
edge *l=graph[t].link;
while(l){
if(dist[l->v]>dist[t]+l->val&&vis[l->v]){
dist[l->v]=dist[t]+l->val;
if(!inque[l->v])
q.push(l->v),inque[l->v]=1;
}
l=l->link;
}
}
}

int main(){
build();
dfs(END);
int change[11000]={0};
for(int i=1;i<=n;i++){
edge *l=graph[i].link;
while(l){
if(!vis[l->v]){
change[i]=1;
break;
}
l=l->link;
}
}
for(int i=1;i<=n;i++)
if(change[i]) vis[i]=0;
for(int i=1;i<=n;i++)
dist[i]=43964396;
spfa(START);
if(dist[END]==43964396)
printf("-1");
else
printf("%d",dist[END]);
return 0;
}

0

noip111 LV 7 @ 2016-11-07 21:44:52

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
const int maxn=10034;
const int INF=(1<<25);
using namespace std;
vector<int> v[maxn];
vector<int> Lv[maxn];
int n,m,B,D;
int path[maxn],out[maxn];
bool inq[maxn],note[maxn];

void SPFA(int begin,int D)
{
for(int i=1;i<=n;i++)
path[i]=INF;
path[begin]=0;

memset(inq,false,sizeof(inq));
inq[begin]=true;
queue<int>q;
q.push(begin);

int now,to,cost,len;
while(!q.empty())
{
now=q.front();
len=v[now].size();
q.pop();inq[now]=false;
for(int k=0;k<len;k++)
{
to=v[now][k];
cost=1;
// cost=path[now];
if(note[to]&&cost+path[now]<path[to])
{
path[to]=cost+path[now];
if(!inq[to])
{
q.push(to);
inq[to]=true;
}
}
}
}
}

void Input()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
v[from].push_back(to);
out[from]++;
Lv[to].push_back(from);
}
scanf("%d%d",&B,&D);

// dfs(D,1);
// note[D]=true;
for(int i=1;i<=n;i++)
note[i]=true;
for(int i=1;i<=n;i++)
{
if(!out[i]&&i!=D)
{
for(int k=0;k<Lv[i].size();k++)
{
int v0=Lv[i][k];
note[v0]=false;
}
}
}
note[B]=note[D]=true;
SPFA(B,D);
if(path[D]==INF)
cout<<"-1";
else
cout<<path[D];
}

int main()
{
Input();
return 0;
}

0

noip111 LV 7 @ 2016-11-07 21:44:29

测试数据 #0: Accepted, time = 15 ms, mem = 912 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 908 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 908 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 908 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 908 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 912 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1056 K

0

linhui LV 9 @ 2016-09-07 00:12:56

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 10000 + 10;

vector<int> map[MAXN], check[MAXN];
bool vis[MAXN], could[MAXN];
int tep[MAXN];

void c_DFS(int s){
for(int i=0; i<check[s].size(); i++){
int u = check[s][i];
if(!vis[u]){
vis[u] = 1;
c_DFS(u);
}
}
}

int BFS(int s, int t){
queue<int> que;
memset(vis, 0, sizeof(vis));
if(!could[s]) return -1;
vis[s] = 1;
que.push(s);
while(!que.empty()){
int now = que.front();
que.pop();
if(now == t) return tep[now];
for(int i=0; i<map[now].size(); i++){
int v = map[now][i];
if(vis[v] || !could[v]) continue;
vis[v] = 1;
tep[v] = tep[now] + 1;
que.push(v);
}
}
return -1;
}

int main()
{
int n, m, s, t, x, y;
cin>>n>>m;
for(int i=1; i<=n; i++) could[i] = 1;
for(int i=1; i<=m; i++){
cin>>x>>y;
map[x].push_back(y);
check[y].push_back(x);
}
cin>>s>>t;

vis[t] = 1;
c_DFS(t);

for(int i=1; i<=n; i++)
if(!vis[i]){
could[i] = 0;
for(int j=0; j<check[i].size(); j++){
int now = check[i][j];
could[now] = 0;
}
}

cout<<BFS(s, t);
return 0;
}
DFS + BFS PS。只用存一个图就好了。。。代码有点丑

0

2233702013 LV 8 @ 2016-08-23 18:19:40

本蒟蒻的思想和楼下的差不太多……只不过本蒟蒻用的是BFS。
建立图的同时建个反向图，然后从终点开始BFS，能到达的点就用个布尔型数组记录下来。BFS完毕以后枚举所有点，看哪个点没有BFS过，说明它无法到达终点，所以要标记他的前驱节点为无法到达，所以把它加入到队列中【这里必须加入到队列中，不能直接标记前驱节点，因为可能在后面枚举时会枚举到它的前驱结点，导致一整条路都被标记为无法到达】，然后再把队列中的所有点的前驱节点标记为不能到达（这里不能把它的前驱节点也加入到队列中！），然后SPFA，松弛时判断是否可以到达。
代码如下（这是我写过的提高组的代码中最丑最长的）:
c++ #include <iostream> #include <vector> #include <queue> #define inf 99999999 using namespace std; int n,m,s,t,dis[10005]; bool book[10005],is_inque[10005]; vector<int> list[10005],dlist[10005]; queue<int> que; int main() { ios::sync_with_stdio(0); cin>>n>>m; for(int i=1;i<=m;i++) { int n1,n2; cin>>n1>>n2; if(n1!=n2)list[n1].push_back(n2);dlist[n2].push_back(n1); } cin>>s>>t; que.push(t); while(!que.empty()) { int load=que.front(); book[load]=1; que.pop(); int dsize=dlist[load].size(); for(int i=0;i<dsize;i++)if(!book[dlist[load][i]])que.push(dlist[load][i]); } for(int i=1;i<=n;i++) { if(!book[i])que.push(i); dis[i]=inf; } while(!que.empty()) { int load=que.front(); que.pop(); int dsize=dlist[load].size(); for(int i=0;i<dsize;i++)book[dlist[load][i]]=0; } book[s]=1; que.push(s); dis[s]=0; while(!que.empty()) { int load=que.front(); que.pop(); is_inque[load]=0; int size=list[load].size(); for(int i=0;i<size;i++) if(book[list[load][i]]&&dis[load]+1<dis[list[load][i]]) { dis[list[load][i]]=dis[load]+1; if(!is_inque[list[load][i]]) { que.push(list[load][i]); is_inque[list[load][i]]=1; } } } if(dis[t]!=inf)cout<<dis[t]; else cout<<-1; return 0; }

0

chronix LV 8 @ 2016-07-16 09:59:35

建图时建立图与反向图
反向图dfs从终点开始，看看那些点可以到达终点
再在原图上依次访问不可到达终点的，把他们出边指向的点储存
标记刚刚储存的点为不可到达
最后原图SPFA
```c++
#include <cstdio>
#include <cstring>
#include <queue>
#define max 1000

using std::queue;

struct edge{
int d,v;
struct edge *link;
};

int top=0,n,m;
int st,end;
edge graph[10010]={0};
edge g2[10010]={0};
edge node[400040];

void read(int s,int d,int v){
edge *l;
l=&node[top];
l->d=d;
l->v=v;
l->link=graph[s].link;
graph[s].link=l;
top++;
}

void read2(int s,int d,int v){
edge *l;
l=&node[top];
l->d=d;
l->v=v;
l->link=g2[s].link;
g2[s].link=l;
top++;
}

void build(){
scanf("%d%d",&n,&m);
int s,d,v;
for(int i=1;i<=m;i++){
scanf("%d%d",&s,&d);
read(s,d,1);
read2(d,s,1);
}
}

//SPFA

int inque[10010]={0};
int dist[10010];
queue <int> q;
int acc[10010]={0};

void spfa(int s){
memset(dist,0x7F,sizeof(dist));
q.push(s);
dist[s]=0;
inque[s]=1;
edge *l;
int t;
while(!q.empty()){
t=q.front();
q.pop();
inque[t]=0;
l=graph[t].link;
while(l){
if(dist[t]+l->v<dist[l->d]){
dist[l->d]=dist[t]+l->v;
if(!inque[l->d]&&acc[l->d]){
q.push(l->d);
inque[l->d]=1;
}
}
l=l->link;
}
}
}

//DFS

void dfs(int s){
edge *l;

acc[s]=1;
l=g2[s].link;
while(l){
if(!acc[l->d])
dfs(l->d);
l=l->link;
}
}

int main(){
//freopen("in.txt","r",stdin);
build();
scanf("%d%d",&st,&end);
dfs(end);
int chg[10010]={0};
for(int i=1;i<=n;i++){
edge *l;
if(acc[i]==0){
l=g2[i].link;
while(l){
chg[l->d]=1;
l=l->link;
}
}
}

for(int i=1;i<=n;i++)
if(chg[i]==1)
acc[i]=0;
if(acc[st]==0){
printf("-1");
return 0;
}
spfa(st);
printf("%d",dist[end]);
return 0;
}
```

0

tootal (hzq) LV 9 @ 2016-07-05 17:11:22

再次练习了下spfa。。
~~~
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,u,v,s,f,i;
int dis[100005],used[100005],vis[100005];
queue<int>q1,q2;
vector<int>p1[100005];
vector<int>p2[100005];
vector<int>::iterator it;
void spfa2(){
for(int i=1;i<=n;i++){
dis[i]=INF;
}
dis[f]=0;
vis[f]=1;
q2.push(f);
while(!q2.empty()){
int t=q2.front();
q2.pop();
for(it=p2[t].begin();it!=p2[t].end();it++){
if(dis[t]+1<dis[*it]){
dis[*it]=dis[t]+1;
if(!vis[*it]){
q2.push(*it);
vis[*it]=1;
}
}
}
}
}
void spfa1(){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
dis[i]=INF;
}
dis[s]=0;
vis[s]=1;
q1.push(s);
while(!q1.empty()){
int t=q1.front();
q1.pop();
for(it=p1[t].begin();it!=p1[t].end();it++){
if(dis[t]+1<dis[*it]&&!used[*it]){
dis[*it]=dis[t]+1;
if(!vis[*it]){
q1.push(*it);
vis[*it]=1;
}
}
}
}
}
int main(){
freopen("input.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&u,&v);
p1[u].push_back(v);
p2[v].push_back(u);
}
scanf("%d%d",&s,&f);
spfa2();
for(int i=1;i<=n;i++){
if(dis[i]==INF){
used[i]=1;
for(it=p2[i].begin();it!=p2[i].end();it++){
used[*it]=1;
}
}
}
spfa1();
if(dis[f]==INF)printf("-1\n");
else printf("%d\n",dis[f]);
return 0;
}
~~~

题解

45 条题解

寻找道路

信息

状态

开发

支持

题解

45 条题解

寻找道路

信息

状态

开发

支持

还没有账户？

登录