สมมติว่ามี n เมืองและถนน m เชื่อมต่อกัน ถนนแต่ละเส้นเป็นทางเดียว และต้องใช้เวลาระยะหนึ่งในการเดินทางจากเมืองต้นทางไปยังเมืองปลายทาง ข้อมูลของถนนจะแสดงในถนนแถวเรียงซึ่งแต่ละองค์ประกอบอยู่ในรูปแบบ (ต้นทาง ปลายทาง เวลา) ตอนนี้มีคนเดินทางจากเมืองหนึ่งไปยังอีกเมืองหนึ่งและการเดินทางจะต้องไป-กลับ การเดินทางสามารถเรียกได้ว่าไป - กลับเมื่อบุคคลนั้นเริ่มจากเมืองใดเมืองหนึ่ง ผ่านถนนหนึ่งเส้นขึ้นไป และสิ้นสุดการเดินทางในเมืองเดียวกัน ดังนั้น สำหรับแต่ละเมือง เราต้องพิจารณาว่าสามารถเดินทางไปกลับจากเมืองนั้น ๆ ได้หรือไม่ หากเป็นไปได้ ให้พิมพ์เวลาที่ใช้ในการเดินทางไปกลับหรือมิฉะนั้นให้พิมพ์ -1
ดังนั้น หากอินพุตเป็น n =4, m =4, ถนน ={{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}} จากนั้นผลลัพธ์จะเป็น:26 26 26 26 จากแต่ละเมืองจะต้องใช้เวลา 26 เพื่อเดินทางไปกลับ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
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]) ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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;
} อินพุต
4, 4, {{1, 2, 5}, {2, 3, 8}, {3, 4, 7}, {4, 1, 6}}
ผลลัพธ์
26 26 26 26
