Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <deque>
- #include <iostream>
- #include <string>
- #include <set>
- #include <utility>
- #include <vector>
- using namespace std;
- struct Graph {
- vector<vector<int>> graph;
- vector<vector<int>> new_graph;
- vector<int> path;
- vector<bool> visited;
- int time;
- vector<int> times_;
- int count_vert;
- explicit Graph(int n, vector<int> times) :
- graph(n),
- new_graph(n),
- visited(n, false),
- time(0),
- times_(std::move(times)),
- count_vert(0) {}
- void dfs2(int now);
- };
- void Graph::dfs2(int now) {
- visited[now] = true;
- for (auto neig : new_graph[now]) {
- if (!visited[neig]) {
- dfs2(neig);
- }
- }
- path.push_back(now);
- time += times_[now];
- ++count_vert;
- }
- int main() {
- int N;
- std::cin >> N;
- vector<int> times;
- for (int t = 0; t < N; ++t) {
- int time;
- cin >> time;
- times.push_back(time);
- }
- Graph g(N, times);
- for (int now = 1; now <= N; ++now) {//отсчёт как от пользователя
- int count;
- cin >> count;
- for (int j = 0; j < count; ++j) {
- int neig;
- std::cin >> neig;
- g.graph[neig - 1].emplace_back(now - 1);
- g.new_graph[now - 1].emplace_back(neig - 1);
- }
- }
- g.visited.assign(N, false);
- g.dfs2(0);
- cout << g.time << " " << g.count_vert << '\n';
- for (auto vert:g.path) {
- cout << vert + 1 << ' ';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement