3月份一個(gè)偶然的機(jī)會(huì)刷了一道算法題，當(dāng)時(shí)折騰了好久，趁現(xiàn)在有空趕緊記錄一下。
原題地址：Rust&Murderer

題目描述

Detective Rust is investigating a homicide and he wants to chase down the murderer. The murderer knows he would definitely get caught if he takes the main roads for fleeing, so he uses the village roads (or side lanes) for running away from the crime scene.

Rust knows that the murderer will take village roads and he wants to chase him down. He is observing the city map, but it doesn't show the village roads (or side lanes) on it and shows only the main roads.

The map of the city is a graph consisting nodes (labeled to ) where a specific given node represents the current position of Rust and the rest of the nodes denote other places in the city, and an edge between two nodes is a main road between two places in the city. It can be suitably assumed that an edge that doesn't exist/isn't shown on the map is a village road (side lane). That means, there is a village road between two nodes and iff(if and only if) there is no city road between them.

Rust wants to calculate the shortest distance from his position (Node ) to all the other places in the city if he travels using the village roads (side lanes).

Note: The graph/map of the city is ensured to be a sparse graph.

分析

問(wèn)題本質(zhì)上就是給定一個(gè)無(wú)權(quán)無(wú)向圖，從S點(diǎn)出發(fā)，只能走不連通的路徑(side lane)，求S點(diǎn)到每個(gè)點(diǎn)的最短路徑。

• 基礎(chǔ)思路是：用一個(gè)map存儲(chǔ)所有的不連通的路徑，然后用最短路徑算法求出S點(diǎn)到每個(gè)點(diǎn)的路徑。但是注意原始圖是一個(gè)稀疏圖，存儲(chǔ)不連通的路徑的話不會(huì)卡時(shí)間但是會(huì)卡空間。
• 因?yàn)槭菬o(wú)權(quán)圖，不需要用Dijkstra算法，直接BFS即可。BFS的方法就是用一個(gè)隊(duì)列來(lái)存儲(chǔ)每一層的結(jié)點(diǎn)，就像二叉樹(shù)的層次遍歷那樣。
• 每次執(zhí)行BFS時(shí)，從S出發(fā)，每下降一層距離就加1 。 關(guān)鍵是怎么知道某個(gè)節(jié)點(diǎn)到哪些節(jié)點(diǎn)不連通。為了解決卡空間的問(wèn)題，可以構(gòu)造一個(gè)hashset來(lái)存儲(chǔ)沒(méi)有訪問(wèn)過(guò)的節(jié)點(diǎn)。每次從這個(gè)hashset里遍歷，看是不是連通。這樣就OK了。

代碼實(shí)現(xiàn)

#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int caseNumber;
    cin >> caseNumber;
    for (int i = 0; i < caseNumber; i ++){
        int cityNumber;
        int pathNumber;
        cin >> cityNumber >> pathNumber;

        unordered_map<int, unordered_set<int> > mainPath;
        unordered_set<int> unvisitedCities;

        for (int j = 1; j < cityNumber + 1; j ++){
            unvisitedCities.insert(j);
        }
       
        for (int j = 0; j < pathNumber; j ++){
            int src;
            int dst;
            cin >> src >> dst;
            mainPath[src].insert(dst);
            mainPath[dst].insert(src);
        }
       
        int derectiveLocation;
        cin >> derectiveLocation;
        int distance[cityNumber + 1];
        for (int j = 0; j < cityNumber + 1; j ++)
            distance[j] = -1;
        distance[derectiveLocation] = 0;
        queue<int> bfsQueue;

        bfsQueue.push(derectiveLocation);

        while (bfsQueue.size() && unvisitedCities.size()){
            int front = bfsQueue.front();
            unordered_set<int> tempSet(unvisitedCities);
            for (auto p : mainPath[front]){
                tempSet.erase(p);
            }
            for (auto index : tempSet) {
                if (distance[index] == -1) {
                    bfsQueue.push(index);
                    distance[index] = distance[front] + 1;
                }
            }
            for (auto c : tempSet){
                unvisitedCities.erase(c);
            } 
            bfsQueue.pop();
        }
        int realDistance[cityNumber ];
        for (int j = 1; j < derectiveLocation; j ++){
            realDistance[j] = distance[j];
        }
        for (int j = derectiveLocation + 1; j < cityNumber + 1; j ++){
            realDistance[j - 1] = distance[j];
        }
        printf("%d", realDistance[1]);
        for (int j = 2; j < cityNumber; j ++){
            printf(" %d", realDistance[j]);
        }
        printf("\n");
    }
    return 0;
}