Giả sử, có n thành phố và m đường nối chúng. Mỗi con đường là một chiều và cần một khoảng thời gian cụ thể để đi từ thành phố nguồn đến thành phố đích. Thông tin của các con đường được cung cấp trong các mảng đường trong đó mỗi phần tử có định dạng (nguồn, đích, thời gian). Bây giờ, một người đang đi du lịch từ thành phố này đến thành phố khác và chuyến đi phải là một chuyến đi khứ hồi. Một chuyến đi có thể được gọi là khứ hồi khi một người bắt đầu từ một thành phố cụ thể, đi qua một hoặc nhiều con đường và kết thúc chuyến đi trong cùng một thành phố. Vì vậy, đối với mỗi thành phố, chúng ta phải xác định xem có thể có một chuyến đi khứ hồi từ thành phố cụ thể đó hay không. Nếu có thể, hãy in thời gian cần thiết để thực hiện chuyến khứ hồi hoặc nếu không, hãy in -1.
Vì vậy, nếu đầu vào là n =4, m =4, đường ={{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}} , khi đó kết quả sẽ là:26 26 26 26. Từ mỗi thành phố, cần thời gian 26 để thực hiện một chuyến đi khứ hồi.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
Define one 2D array graph(n) of pairs
for initialize i := 0, when i < m, update (increase i by 1), do:
x := first value of roads[i]
y := second value of roads[i]
z := third value of roads[i]
decrease x and y by 1
insert pair (y, z) at the end of graph[x]
for initialize i := 0, when i < n, update (increase i by 1), do:
q := a new priority queue
Define an array dst
insert pair (0, i) at the top of q
while size of q is non-zero, do:
pair p := top value of q
delete the top element from q
dt := first value of p
curr := second value of p
if dst[curr] is same as 0, then:
dst[curr] := dt
Come out from the loop
if dst[curr] is not equal to -1, then:
Ignore following part, skip to the next iteration
dst[curr] := dt
for element next in graph[curr], do:
tp := first value of next
cst := second value of next
insert pair(dt + cst, tp) at the top of q
if dst[i] is same as 0, then:
dst[i] := -1
print(dst[i]) Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int modval = (int) 1e9 + 7;
#define N 100
void solve(int n, int m, vector<tuple<int, int, int>> roads ) {
vector<vector<pair<int, int>>> graph(n);
for(int i = 0; i < m; i++) {
int x, y, z;
tie(x, y, z) = roads[i];
x--; y--;
graph[x].emplace_back(y, z);
}
for(int i = 0; i < n; i++) {
priority_queue<pair<int, int>> q;
vector<int> dst(n, -1);
q.emplace(0, i);
while(q.size()){
pair<int, int> p = q.top();
q.pop();
int curr, dt;
tie(dt, curr) = p;
if(dst[curr] == 0) {
dst[curr] = dt;
break;
}
if(dst[curr] != -1)
continue;
dst[curr] = dt;
for(auto next : graph[curr]){
int tp, cst;
tie(tp, cst) = next;
q.emplace(dt + cst, tp);
}
}
if(dst[i] == 0)
dst[i] = -1;
cout<< dst[i]<< endl;
}
}
int main() {
int n = 4, m = 4;
vector<tuple<int, int, int>> roads = {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}};
solve(n, m, roads);
return 0;
} Đầu vào
4, 4, {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}}
Đầu ra
26 26 26 26