C++ 程序确定是否可以从特定城市往返

• Z时代
• 2024-01-10
• 分类：综合

假设有 n 个城市，有 m 条道路连接它们。每条道路都是单向的，从源城市到达目的地城市需要一定的时间。道路信息在数组道路中给出，其中每个元素的格式为（源、目的地、时间）。现在，一个人从一个城市到另一个城市旅行，旅行必须是往返。当一个人从一个特定的城市出发，经过一条或多条道路，并在同一个城市完成旅行时，可以称为往返旅行。因此，对于每个城市，我们必须确定是否可以从该特定城市往返。如果可能，请打印执行往返所需的时间，否则打印 -1。

所以，如果输入像 n = 4, m = 4，roads = {{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

以上是 C++ 程序确定是否可以从特定城市往返 的全部内容， 来源链接： utcz.com/z/297179.html