Advertisement
Art_Uspen

Untitled

Apr 18th, 2021
651
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. #include <deque>
  2. #include <iostream>
  3. #include <string>
  4. #include <set>
  5. #include <utility>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. struct Graph {
  11.     vector<vector<int>> graph;
  12.     vector<vector<int>> new_graph;
  13.     vector<int> path;
  14.     vector<bool> visited;
  15.     int time;
  16.     vector<int> times_;
  17.     int count_vert;
  18.  
  19.     explicit Graph(int n, vector<int> times) :
  20.             graph(n),
  21.             new_graph(n),
  22.             visited(n, false),
  23.             time(0),
  24.             times_(std::move(times)),
  25.             count_vert(0) {}
  26.  
  27.  
  28.     void dfs2(int now);
  29. };
  30.  
  31. void Graph::dfs2(int now) {
  32.     visited[now] = true;
  33.     for (auto neig : new_graph[now]) {
  34.         if (!visited[neig]) {
  35.             dfs2(neig);
  36.         }
  37.     }
  38.     path.push_back(now);
  39.     time += times_[now];
  40.     ++count_vert;
  41. }
  42.  
  43.  
  44. int main() {
  45.     int N;
  46.     std::cin >> N;
  47.     vector<int> times;
  48.     for (int t = 0; t < N; ++t) {
  49.         int time;
  50.         cin >> time;
  51.         times.push_back(time);
  52.     }
  53.     Graph g(N, times);
  54.     for (int now = 1; now <= N; ++now) {//отсчёт как от пользователя
  55.         int count;
  56.         cin >> count;
  57.         for (int j = 0; j < count; ++j) {
  58.             int neig;
  59.             std::cin >> neig;
  60.             g.graph[neig - 1].emplace_back(now - 1);
  61.             g.new_graph[now - 1].emplace_back(neig - 1);
  62.         }
  63.     }
  64.     g.visited.assign(N, false);
  65.     g.dfs2(0);
  66.     cout << g.time << " " << g.count_vert << '\n';
  67.     for (auto vert:g.path) {
  68.         cout << vert + 1 << ' ';
  69.     }
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement