Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· openaiHugging Face Suzhen/CodeChat

C++: Cài đặt thuật toán tìm kiếm đường đi ngắn nhất trên đồ thị. INPUT - Dòng đầu tiên…

  1. User

    C++: Cài đặt thuật toán tìm kiếm đường đi ngắn nhất trên đồ thị.

    INPUT

    • Dòng đầu tiên chứa hai số nguyên v và n. Đây lần lượt là số đỉnh trên đồ thị cùng với số thao tác tìm kiếm.

    • Dòng thứ hai chứa v chuỗi cách nhau bởi khoảng trắng, đây là danh sách các đỉnh trên đồ thị.

    • v dòng tiếp theo trong input, mỗi dòng chứa v số nguyên cách nhau bởi khoảng trắng. Đây là ma trận kề của đồ thị. Nếu số nguyên thứ j trong dòng thứ i của v dòng này có giá trị x khác 0 nghĩa là có một cạnh với độ dài x đi từ đỉnh thứ i đến đỉnh thứ j trong danh sách các đỉnh ở dòng thứ 2 của input.

    • n dòng cuối cùng mỗi dòng chứa hai chuỗi s và u đây là đỉnh bắt đầu và đỉnh kết thúc cần tìm.

    OUTPUT

    Ứng với mỗi yêu cầu tìm kiếm xuất ra hai dòng như sau:

    • Dòng thứ nhất xuất ra đường đi từ đỉnh bắt đầu s đến đỉnh kết thúc u tìm được theo thuật toán Djkstra. Mỗi đỉnh trên đường đi cách nhau bởi khoảng trắng, đỉnh s và u được tính trong đường đi. Nếu không có đường đi xuất ra chuỗi -unreachable-

    • Dòng thứ hai xuất ra số lượng đỉnh đã được phát triển trong quá trình tìm kiếm (tức đỉnh được mở rộng bằng cách thêm các con của nó vào cây tìm kiếm) và độ dài đường đi (nếu không có đường đi thì độ dài xem như zero)

    Thứ tự để xét mở rộng các đỉnh là ngược với thứ tự trong danh sách đỉnh ở hàng thứ hai của input:

    Input 5 3

    T K I U O

    0 8 3 0 1

    3 0 0 9 6

    2 3 0 0 5

    8 2 8 0 0

    8 8 8 0 0

    K U

    I O

    K O

    OUTPUT: K U

    5 9

    I T O

    3 3

    K T O

    3 4

  2. Assistant

    #include #include #include <unordered_map> #include #include

    using namespace std;

    typedef pair<int, int> pii; typedef tuple<int, int, string> tis;

    int main() { // Input int v, n; cin >> v >> n;

    vector<string> vertices(v);
    for (int i = 0; i < v; ++i) {
        cin >> vertices[i];
    }
    
    vector<vector<int>> adj_matrix(v, vector<int>(v));
    for (int i = 0; i < v; ++i) {
        for (int j = 0; j < v; ++j) {
            cin >> adj_matrix[i][j];
        }
    }
    
    // Create a map from vertex name to index
    unordered_map<string, int> vertex_indices;
    for (int i = 0; i < v; ++i) {
        vertex_indices[vertices[i]] = i;
    }
    
    // Dijkstra's algorithm
    for (int t = 0; t < n; ++t) {
        string start, end;
        cin >> start >> end;
        int start_index = vertex_indices[start];
        int end_index = vertex_indices[end];
    
        // Initialize priority queue and other data structures
        priority_queue<tis, vector<tis>, greater<tis>> pq;
        pq.push(make_tuple(0, start_index, start));
        vector<int> distances(v, -1);
        vector<bool> visited(v, false);
        int expanded_vertices = 0;
    
        // Main loop
        while (!pq.empty()) {
            int distance, index;
            string path;
            tie(distance, index, path) = pq.top();
            pq.pop();
    
            if (visited[index]) {
                continue;
            }
            visited[index] = true;
    
            expanded_vertices++;
            if (index == end_index) {
                // Found the shortest path
                cout << path << endl;
                cout << expanded_vertices << " " << distance << endl;
                break;
            }
    
            for (int i = v - 1; i >= 0; --i) {
                if (!visited[i] && adj_matrix[index][i] != 0) {
                    int new_distance = distance + adj_matrix[index][i];
                    if (distances[i] == -1 || new_distance < distances[i]) {
                        distances[i] = new_distance;
                        pq.push(make_tuple(new_distance, i, path + " " + vertices[i]));
                    }
                }
            }
        }
    
        // If no path found
        if (!visited[end_index]) {
            cout << "-unreachable-" << endl;
            cout << expanded_vertices << " 0" << endl;
        }
    }
    
    return 0;
    

    }

  3. User

    C++: Cài đặt thuật toán tìm kiếm đường đi ngắn nhất trên đồ thị.

    INPUT

    • Dòng đầu tiên chứa hai số nguyên v và n. Đây lần lượt là số đỉnh trên đồ thị cùng với số thao tác tìm kiếm.

    • Dòng thứ hai chứa v chuỗi cách nhau bởi khoảng trắng, đây là danh sách các đỉnh trên đồ thị.

    • v dòng tiếp theo trong input, mỗi dòng chứa v số nguyên cách nhau bởi khoảng trắng. Đây là ma trận kề của đồ thị. Nếu số nguyên thứ j trong dòng thứ i của v dòng này có giá trị x khác 0 nghĩa là có một cạnh với độ dài x đi từ đỉnh thứ i đến đỉnh thứ j trong danh sách các đỉnh ở dòng thứ 2 của input.

    • n dòng cuối cùng mỗi dòng chứa hai chuỗi s và u đây là đỉnh bắt đầu và đỉnh kết thúc cần tìm.

    OUTPUT

    Ứng với mỗi yêu cầu tìm kiếm xuất ra hai dòng như sau:

    • Dòng thứ nhất xuất ra đường đi từ đỉnh bắt đầu s đến đỉnh kết thúc u tìm được theo thuật toán Djkstra. Mỗi đỉnh trên đường đi cách nhau bởi khoảng trắng, đỉnh s và u được tính trong đường đi. Nếu không có đường đi xuất ra chuỗi -unreachable-

    • Dòng thứ hai xuất ra số lượng đỉnh đã được phát triển trong quá trình tìm kiếm (tức đỉnh được mở rộng bằng cách thêm các con của nó vào cây tìm kiếm) và độ dài đường đi (nếu không có đường đi thì độ dài xem như zero)

    Thứ tự để xét mở rộng các đỉnh là ngược với thứ tự trong danh sách đỉnh ở hàng thứ hai của input

  4. Assistant

    Dưới đây là mã nguồn cài đặt thuật toán tìm kiếm đường đi ngắn nhất trên đồ thị bằng Dijkstra theo yêu cầu.

    #include <iostream>
    #include <vector>
    #include <unordered_map>
    #include <queue>
    #include <tuple>
    
    using namespace std;
    
    typedef pair<int, int> pii;
    typedef tuple<int, int, string> tis;
    
    int main() {
        // Input
        int v, n;
        cin >> v >> n;
    
        vector<string> vertices(v);
        for (int i = 0; i < v; ++i) {
            cin >> vertices[i];
        }
    
        vector<vector<int>> adj_matrix(v, vector<int>(v));
        for (int i = 0; i < v; ++i) {
            for (int j = 0; j < v; ++j) {
                cin >> adj_matrix[i][j];
            }
        }
    
        // Create a map from vertex name to index
        unordered_map<string, int> vertex_indices;
        for (int i = 0; i < v; ++i) {
            vertex_indices[vertices[i]] = i;
        }
    
        // Dijkstra's algorithm
        for (int t = 0; t < n; ++t) {
            string start, end;
            cin >> start >> end;
            int start_index = vertex_indices[start];
            int end_index = vertex_indices[end];
    
            // Initialize priority queue and other data structures
            priority_queue<tis, vector<tis>, greater<tis>> pq;
            pq.push(make_tuple(0, start_index, start));
            vector<int> distances(v, -1);
            vector<bool> visited(v, false);
            int expanded_vertices = 0;
    
            // Main loop
            while (!pq.empty()) {
                int distance, index;
                string path;
                tie(distance, index, path) = pq.top();
                pq.pop();
    
                if (visited[index]) {
                    continue;
                }
                visited[index] = true;
    
                expanded_vertices++;
                if (index == end_index) {
                    // Found the shortest path
                    cout << path << endl;
                    cout << expanded_vertices << " " << distance << endl;
                    break;
                }
    
                for (int i = v - 1; i >= 0; --i) {
                    if (!visited[i] && adj_matrix[index][i] != 0) {
                        int new_distance = distance + adj_matrix[index][i];
                        if (distances[i] == -1 || new_distance < distances[i]) {
                            distances[i] = new_distance;
                            pq.push(make_tuple(new_distance, i, path + " " + vertices[i]));
                        }
                    }
                }
            }
    
            // If no path found
            if (!visited[end_index]) {
                cout << "-unreachable-" << endl;
                cout << expanded_vertices << " 0" << endl;
            }
        }
    
        return 0;
    }
    

    Mã nguồn trên đọc dữ liệu nhập từ trên xuống dưới theo đúng thứ tự yêu cầu, sau đó dựa vào thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh bắt đầu đến đỉnh kết thúc. Nếu không tìm thấy bất kỳ đường đi nào, mã nguồn sẽ xuất ra chuỗi "unreachable" và các thông tin liên quan.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.