[HackerRank]Rust&Murderer疎図最短経路問題

4273 ワード
3月に偶然アルゴリズムの問題を書いたが、長い間振り回されていたので、今のうちに急いで記録した.原題アドレス: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.
ぶんせき
問題は本質的に無権無方向図を与え,S点から連通しない経路(side lane)しか歩けず,S点から各点への最短経路を求める.
  • の基本構想は、1つのmapですべての不連通の経路を格納し、最短経路アルゴリズムでS点から各点への経路を求めることである.ただし、元の図は疎図であり、接続されていない経路を格納すると時間がかかりませんが、カード空間があります.
  • は無権図であるためDijkstraアルゴリズムを用いる必要はなく,直接BFSでよい.BFSの方法は,ツリーの階層遍歴のように,各階層のノードを1つのキューで格納することである.
  • BFSが実行されるたびに、Sから1段下がるごとに1が加算される.キーは、ノードがどのノードに接続されていないかをどのように知るかです.カードスペースの問題を解決するために、hashsetを構築して、アクセスしたことのないノードを格納することができます.毎回このhashsetから遍歴して、連通しているかどうかを見ます.これでOKです.

    • コード実装
    #include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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 > mainPath;
        unordered_set 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 bfsQueue;

        bfsQueue.push(derectiveLocation);

        while (bfsQueue.size() && unvisitedCities.size()){
            int front = bfsQueue.front();
            unordered_set 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("
    ");
    }
    return 0;
}
    pythonのenumerate()関数の使用方法
    HDU4812