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…
- 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
-
- 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;}
- 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
-
- 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.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.