Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <unordered_map>
- #include <map>
- using namespace std;
- class Reader {
- public:
- Reader() {
- input_ = fopen("input.txt", "r");
- last_ = -1;
- }
- int next_number() {
- if (last_ != -1) {
- int value = last_;
- last_ = -1;
- return value;
- }
- return read<int>().first;
- }
- bool has_number() {
- if (last_ != -1) {
- return true;
- }
- auto rd = read<int>();
- if (!rd.second) {
- return false;
- }
- last_ = read<int>().first;
- return true;
- }
- void reset() {
- fseek(input_, 0, SEEK_SET);
- }
- private:
- template<class T>
- pair<T, bool> read() {
- register int c = 0;
- T x = 0;
- for(; c < '0' || c > '9'; c = fgetc(input_));
- for(; c >= '0' && c <= '9'; c = fgetc(input_)) {
- x = (x << 1) + (x << 3) + c - '0';
- return {x, false};
- }
- return {x, true};
- }
- FILE* input_;
- int last_;
- };
- class Graph {
- public:
- Graph() {
- }
- int edge(size_t a, size_t b) {
- if (a > b)
- swap(a, b);
- if (saved_edges_.find({a, b}) != saved_edges_.end()) {
- return saved_edges_.at({a, b});
- }
- reader_.reset();
- reader_.next_number();
- reader_.next_number();
- while (reader_.has_number()) {
- size_t x = reader_.next_number();
- size_t y = reader_.next_number();
- --x, --y;
- if (x > y)
- swap(x, y);
- int w = reader_.next_number();
- if (a == x && b == y || a == y && b == x) {
- return w;
- }
- if (a == x || b == x || a == y || b == y) {
- saved_edges_.insert({{x, y}, w});
- if (saved_edges_.size() > kMaxSaved) {
- saved_edges_.erase(saved_edges_.begin());
- }
- }
- }
- }
- private:
- const size_t kMaxSaved = 1000000;
- Reader reader_;
- map<pair<size_t, size_t>, int> saved_edges_;
- };
- Graph graph;
- vector<bool> used;
- int n, m;
- vector<int> ans;
- void dfs(int v) {
- ans.push_back(v);
- used[v] = true;
- if (v == n - 1) {
- cout << ans.size() << endl;
- for (auto x : ans) {
- cout << x + 1 << ' ';
- }
- exit(0);
- }
- for (size_t to = 0; to < n; ++to) {
- if (!used[to] && graph.edge(v, to)) {
- dfs(to);
- }
- }
- }
- int main() {
- Reader reader;
- n = reader.next_number();
- m = reader.next_number();
- used.resize(n);
- dfs(0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement