Gym 101170I Iron and Coal（BFS + 思维）题解

题意：有一个有向图，有些点是煤，有些点是铁，但不会同时有铁和煤。现在我要从1出发，占领可以到达的点。问最少占领几个点能同时拥有一个煤和一个铁（1不用占领）。

思路：思路很秀啊。我们从1往外bfs，得到所有点到1的最短路dis[i][0]，然后从所有煤跑bfs得到所有点到煤的最短路dis[i][1]，我们再从所有铁跑bfs得到所有点到铁的最短路dis[i][2]，那么dis[i][0] + dis[i][1] + dis[i][2]就是以i为分界点分别前往煤和铁的占领的最小距离。那么答案就是min{ dis[i][0] + dis[i][1] + dis[i][2] }。

代码：

#include<cmath>

#include<set>

#include<map>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include <iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 1e5 + 10;

const ull seed = 131;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

int n, m, k;

int iron[maxn], coal[maxn], vis[maxn];

vector<int> G[maxn], g[maxn];

int dis[maxn][3];

struct node{

    int x;

    int step;

};

void bfs1(){

    for(int i = 1; i <= n; i++) vis[i] = 0;

    queue<node> q;

    while(!q.empty()) q.pop();

    vis[1] = 1;

    dis[1][0] = 0;

    node a, b;

    a.x = 1, a.step = 0;

    q.push(a);

    while(!q.empty()){

        a = q.front();

        q.pop();

        for(int i = 0; i < G[a.x].size(); i++){

            int v = G[a.x][i];

            if(vis[v]) continue;

            vis[v] = 1;

            dis[v][0] = a.step + 1;

            b.x = v, b.step = a.step + 1;

            q.push(b);

        }

    }

}

void bfs2(){

    for(int i = 1; i <= n; i++) vis[i] = 0;

    queue<node> q;

    while(!q.empty()) q.pop();

    node a, b;

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

        if(iron[i]){

            vis[i] = 1;

            dis[i][1] = 0;

            a.x = i, a.step = 0;

            q.push(a);

        }

    }

    while(!q.empty()){

        a = q.front();

        q.pop();

        for(int i = 0; i < g[a.x].size(); i++){

            int v = g[a.x][i];

            if(vis[v]) continue;

            vis[v] = 1;

            dis[v][1] = a.step + 1;

            b.x = v, b.step = a.step + 1;

            q.push(b);

        }

    }

}

void bfs3(){

    for(int i = 1; i <= n; i++) vis[i] = 0;

    queue<node> q;

    while(!q.empty()) q.pop();

    node a, b;

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

        if(coal[i]){

            vis[i] = 1;

            dis[i][2] = 0;

            a.x = i, a.step = 0;

            q.push(a);

        }

    }

    while(!q.empty()){

        a = q.front();

        q.pop();

        for(int i = 0; i < g[a.x].size(); i++){

            int v = g[a.x][i];

            if(vis[v]) continue;

            vis[v] = 1;

            dis[v][2] = a.step + 1;

            b.x = v, b.step = a.step + 1;

            q.push(b);

        }

    }

}

int main(){

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

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

        iron[i] = coal[i] = 0;

        G[i].clear();

        g[i].clear();

        memset(dis[i], INF, sizeof(dis[i]));

    }

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

        int u;

        scanf("%d", &u);

        iron[u] = 1;

    }

    for(int i = 1; i <= k; i++){

        int u;

        scanf("%d", &u);

        coal[u] = 1;

    }

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

        int p, u, v;

        scanf("%d", &p);

        u = i;

        while(p--){

            scanf("%d", &v);

            G[u].push_back(v);

            g[v].push_back(u);

        }

    }

    bfs1();

    bfs2();

    bfs3();

    int ans = INF;

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

        if(dis[i][0] == INF || dis[i][1] == INF || dis[i][2] == INF) continue;

        ans = min(ans, dis[i][0] + dis[i][1] + dis[i][2]);

    }

    if(ans < INF) printf("%d\n", ans);

    else printf("impossible\n");

    return 0;

}

巴特西

Gym 101170I Iron and Coal（BFS + 思维）题解

最新文章

热门文章