BFS 用映射 C++ 替换数组

Question

如何在 BFS 算法中将普通数组 int playersStartPos[100] 替换为 std::map？该算法找到所有两个顶点之间的最短路径。它有效，但在某些情况下，处理所有顶点需要超过 1 秒的时间。所以我必须用 std::map 替换这个循环 for (int j = 0; j < K; j++) { //BAAAADDDDDD 并按键搜索。但它看起来效果更差（应该更好我知道它 100%）。如何修改算法以使用 std::map？。谢谢。

**INPUT**
7 3 
1 1 
2 0 2 
2 1 4 
1 4 
3 2 3 5 
2 4 6 
1 5 
0 3 6

**OUTPUT**
0 4 5 
4 0 3 
5 3 0 
1 2

#include <iostream>
#include <stdio.h>

#include <vector>
#include <queue>
#include <map>

using namespace std;

vector<vector<int>> adjList;
int N = 0; //vertices quantity
int K = 0; //players quantity
int playersStartPos[100];
int res[100][100];

void read()
{
    FILE* fp = fopen("input2.txt", "r");
    fscanf(fp, "%d", &N);
    fscanf(fp, "%d", &K);

    for (int i = 0; i < N; i++) {
        int size = 0;
        fscanf(fp, "%d", &size);

        vector<int> adjacency(size);
        for (int j = 0; j < size; j++) {
            int to = 0;
            fscanf(fp, "%d", &to);
            adjacency[j] = to;
        }

        adjList.push_back(adjacency);
    }

    for (int player = 0; player < K; player++) {
        int pos = 0;
        fscanf(fp, "%d", &pos);

        //cout << pos << " ";
        playersStartPos[player] = pos;
    }

    //fclose(fp);
}

int bfs(int start, int ind)
{
    queue<int> q;
    vector<bool> used(N, 0);
    vector<int> path(N);

    q.push(start);
    used[start] = true;
    path[start] = -1;

    while (!q.empty()) {

        int currentVertex = q.front();
        q.pop();

        for (size_t i = 0; i < adjList[currentVertex].size(); ++i) {
            int to = adjList[currentVertex][i];

            if (!used[to]) {

                path[to] = path[currentVertex] + 1;

                used[to] = true;
                q.push(to);

                for (int j = 0; j < K; j++) { //BAAAADDDDDD

                    if (to == playersStartPos[j]) {
                        res[ind][j] = path[to] + 1;
                    }
                }
            }
        }
    }

    return 0;
}

void find()
{
    for (int i = 0; i < K; i++) {
        bfs(playersStartPos[i], i);
    }
}

void write()
{
    int min = N;
    int one = 0;
    int two = 0;

    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {

            if (res[i][j] == 0) {
                continue;
            }

            if (min > res[i][j]) {
                min = res[i][j];

                one = i;
                two = j;
            }
        }
    }

    FILE* fp = fopen("output.txt", "w");

    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            fprintf(fp, "%d ", res[i][j]);
        }
        fprintf(fp, "%c", '\n');
    }

    fprintf(fp, "%d %d\n", one, two);
    //fclose(fp);
}

int main()
{
    read();

    find();

    write();

    return 0;
}

更新地图

#include <iostream>
#include <stdio.h>

#include <vector>
#include <queue>
#include <map>

using namespace std;

vector<vector<int>> adjList;
int N = 0; //vertices quantity
int K = 0; //players quantity
map<int, int> playersStartPos;
//int playersStartPos[100];
int res[100][100];

void read()
{
    FILE* fp = fopen("input2.txt", "r");
    fscanf(fp, "%d", &N);
    fscanf(fp, "%d", &K);

    for (int i = 0; i < N; i++) {
        int size = 0;
        fscanf(fp, "%d", &size);

        vector<int> adjacency(size);
        for (int j = 0; j < size; j++) {
            int to = 0;
            fscanf(fp, "%d", &to);
            adjacency[j] = to;
        }

        adjList.push_back(adjacency);
    }

    for (int player = 0; player < K; player++) {
        int pos = 0;
        fscanf(fp, "%d", &pos);

        //cout << pos << " ";
        playersStartPos[player] = pos;
    }

    /*for (int i = 0; i < adjList.size(); i++) {
    cout << "From: " << i << " to: ";

    for (int j = 0; j < adjList[i].size(); j++) {
    cout << " " << adjList[i][j];
    }

    cout << endl;
    }*/

    //fclose(fp);
}

int bfs(int start, int ind)
{
    queue<int> q;
    vector<int> used(N, 0);
    vector<int> path(N);

    q.push(start);
    used[start] = true;
    path[start] = -1;

    while (!q.empty()) {

        int currentVertex = q.front();
        q.pop();

        for (size_t i = 0; i < adjList[currentVertex].size(); ++i) {
            int to = adjList[currentVertex][i];

            if (!used[to]) {

                path[to] = path[currentVertex] + 1;

                used[to] = 1;
                q.push(to);

                for (int j = 0; j < K; j++) {

                    auto it = playersStartPos.find(j);
                    if (it == playersStartPos.end()) continue;

                    if (to == it->second) {
                    //if (to == playersStartPos[j]) {

                        //cout << path[to] + 1 << endl;

                        res[ind][it->first] = path[to] + 1;
                        //res[ind][j] = path[to] + 1;

                        //break;
                    }
                }
            }
        }
    }

    return 0;
}

void find()
{
    for (int i = 0; i < K; i++) {
        bfs(playersStartPos[i], i);
    }
}

void write()
{
    int min = N;
    int one = 0;
    int two = 0;

    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {

            if (res[i][j] == 0) {
                continue;
            }

            if (min > res[i][j]) {
                min = res[i][j];

                one = i;
                two = j;
            }
        }
    }

    FILE* fp = fopen("output.txt", "w");

    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            fprintf(fp, "%d ", res[i][j]);
        }
        fprintf(fp, "%c", '\n');
    }

    fprintf(fp, "%d %d\n", one, two);
    //fclose(fp);
}

int main()
{
    read();

    find();

    write();

    return 0;
}

Answer 1

这里是解决方案

#include <iostream>
#include <stdio.h>

#include <vector>
#include <queue>
#include <map>

using namespace std;

vector<vector<int>> adjList;
int N = 0; //vertices quantity
int K = 0; //players quantity
map<int, int> playersStartPos;
int res[100][100];

void read()
{
    FILE* fp = fopen("input.txt", "r");
    fscanf(fp, "%d", &N);
    fscanf(fp, "%d", &K);

    for (int i = 0; i < N; i++) {
        int size = 0;
        fscanf(fp, "%d", &size);

        vector<int> adjacency(size);
        for (int j = 0; j < size; j++) {
            int to = 0;
            fscanf(fp, "%d", &to);
            adjacency[j] = to;
        }

        adjList.push_back(adjacency);
    }

    for (int player = 0; player < K; player++) {
        int vertex = 0;
        fscanf(fp, "%d", &vertex);
        playersStartPos[vertex] = player;
    }

    fclose(fp);
}

int bfs(int start, int ind)
{
    queue<int> q;
    vector<int> used(N, 0);
    vector<int> path(N);

    q.push(start);
    used[start] = true;
    path[start] = -1;

    while (!q.empty()) {

        int currentVertex = q.front();
        q.pop();

        for (size_t i = 0; i < adjList[currentVertex].size(); ++i) {
            int to = adjList[currentVertex][i];

            if (!used[to]) {

                path[to] = path[currentVertex] + 1;

                used[to] = 1;
                q.push(to);

                auto it = playersStartPos.find(to);
                if (it == playersStartPos.end()) continue;

                if (to == it->first) {
                    res[ind][it->second] = path[to] + 1;
                }
            }
        }
    }

    return 0;
}

void find()
{
    map<int, int>::iterator it;
    for (it = playersStartPos.begin(); it != playersStartPos.end(); it++) {
        bfs(it->first, it->second);
    }
}

void write()
{
    int min = N;
    int one = 0;
    int two = 0;

    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {

            if (res[i][j] == 0) {
                continue;
            }

            if (min > res[i][j]) {
                min = res[i][j];

                one = i;
                two = j;
            }
        }
    }

    FILE* fp = fopen("output.txt", "w");

    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            fprintf(fp, "%d ", res[i][j]);
        }
        fprintf(fp, "%c", '\n');
    }

    fprintf(fp, "%d %d\n", one, two);

    fclose(fp);
}

int main()
{
    read();

    find();

    write();

    return 0;
}

BFS 用映射 C++ 替换数组

BFS replace an array with a map C++

c++

breadth-first-search

stdmap