This is the 20th day of my participation in the Genwen Challenge

815. Bus routes

You are given an array routes representing a series of bus routes, where each routes[I] represents a bus route on which the i-th bus will cycle.

For example, routes[0] = [1, 5, 7] means that the 0 bus will always follow the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 ->… Such station routes are driven. Now from source station (not on the bus at the beginning), you’re going to Target Station. Bus only.

Find the minimum number of buses. If it is impossible to reach the terminal station, return -1.

Example 1:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6Copy the code

Example 2:

Input: routes = [[7, 12],,5,15 [4], [6], [15] 3,,12,13 [9]], the source = 15, target = 12 output: 1Copy the code

Tip:

  • 1 <= routes.length <= 500.
  • 1 <= routes[i].length <= 105
  • All values in routes[I] are different
  • sum(routes[i].length) <= 105
  • 0 <= routes[i][j] < 106
  • 0 <= source, target < 106

Methods a

As shown in the figure, we regard each route as a point, so that it can be regarded as the shortest circuit problem of finding the weight of 1 from the point containing source to the point containing target, which can be associated with wide search. In addition, there can be many points containing the source, which translates into a multi-source shortest circuit problem.

Details: use a hash table to record specific bus stops in which lines; After enumeration of a bus stop, the point in the hash table is deleted to prevent repeated enumeration, which is only meaningful when the queue is entered for the first time. Therefore, the point can be deleted after enumeration, ensuring that the process of building the graph is linear.

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) return 0;
        int n = routes.size(a); unordered_map<int, vector<int>> g; / / a hash table
        queue<int> q;
        vector<int> dist(n + 1.1e8); // Record the shortest distance to that point (line)
        for (int i = 0; i < n; i ++ ) // Find the point containing the source.
            for (auto x : routes[i]) {
                if (x == source) {
                    dist[i] = 1; / / get on the bus
                    q.push(i); / / team
                }
                g[x].push_back(i);
            }

        while (q.size()) {
            int t = q.front(a); q.pop(a);for (auto x : routes[t]) {
                if (x == target) return dist[t]; // If it is the destination station, return
                for (auto y : g[x]) {
                    if (dist[y] > dist[t] + 1) { // If the line has not been visited, add the line to the queue
                        dist[y] = dist[t] + 1;
                        q.push(y);
                    }
                }
                g.erase(x); // The bus stop was deleted when traversal was complete}}return - 1; }};Copy the code

Time complexity: O(n2∑inri)O(n^2\ Sum_i ^nr_i)O(n2∑ Inri), where n represents the type of bus and r_i represents the number of stops that the ith bus can reach.