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