题解

45 条题解

  • 7
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2017-02-14 16:25:47

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

  • 0
    @ 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;
    }

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

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

  • 0
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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;
    }
    ~~~

信息

ID
1909
难度
7
分类
图结构 点击显示
标签
递交数
3974
已通过
882
通过率
22%
被复制
4
上传者