题解 | #MT16 公交车#(模拟建图+广度优先搜索)

解题思路

1.同条路线的站点互通只需要一辆公交车即可,建立虚拟节点连接同条公交路线的各个站点,以此建图;每条公交路线的虚拟节点不一样,且不能与实际节点重合,虚拟节点编号可考虑在一个基础值之上递增;从source到target的路径数除以2即为最小代价;

代码

#include <bits/stdc++.h>

using namespace std;

int bfs(unordered_map<int, vector<int>>& g, vector<bool>& isVisited, int t){ //返回最小代价,不能到达返回-1
    queue<int> q;
    q.push(1);
    isVisited[1] = true;
    int curSize, step = -1;
    while(!q.empty()){
        curSize = q.size();
        step++;
        for(int i = 0; i < curSize; i++){
            int node = q.front();
            if(node == t) return step / 2; //注意这里需要除以2
            q.pop();
            for(auto& e : g[node]){
                if(isVisited[e]) continue;
                q.push(e);
                isVisited[e] = true;
            }
        }
    }
    return -1;
}

int main(){
    int n, m;
    while(cin >> n >> m){
        unordered_map<int, vector<int>> g;
        vector<bool> isVisited(n + m + 1); //注意还有虚拟节点(否则数组越界)
        int t;
        for(int i = 1; i <= m; i++){ //每个班车路线共用一个虚拟节点n+i
            cin >> t;
            int v;
            for(int j = 0; j < t; j++){
                cin >> v;
                if(v < 1 || v > n) continue; //当站点不合法时,不加入图中
                g[n + i].push_back(v);
                g[v].push_back(n + i);
            }
        }
        int minCost = bfs(g, isVisited, n);
        cout << minCost << endl;
    }
    return 0;
}