特定の都市からの往復が可能かどうかを調べるC++プログラム

n個の都市があり、m個の道路がそれらを接続しているとします。各道路は一方向であり、出発地の都市から目的地の都市に到達するのに特定の時間がかかります。道路の情報は、各要素が（ソース、宛先、時間）の形式である配列道路で提供されます。今、人はある都市から別の都市に旅行していて、その旅行は往復でなければなりません。人が特定の都市から出発し、1つまたは複数の道路を通過し、同じ都市で旅行を終了する場合、旅行は往復と呼ばれます。したがって、各都市について、その特定の都市からの往復が可能かどうかを判断する必要があります。可能であれば、往復の実行に必要な時間を印刷するか、-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