Longest route

#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <queue>
#include <vector>

// Debug printing
#ifdef DEBUG
#define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args)
#else
#define deb(fmt, args...)
#endif

using namespace std;
using ll = long long;

void print_array(vector<int> in, const string title = "Vector")
{
	cout << title << " [\n";
	for (const auto &el : in) {
		cout << el << " ";
	}
	cout << "\n] END\n";
}

void print_matrix(vector<vector<int> > in, const string title = "Matrix")
{
	cout << title << " [\n";
	for (unsigned int i = 0; i < in.size(); i++) {
		cout << "row " << i << ": ";
		for (unsigned int j = 0; j < in[i].size(); j++) {
			cout << in[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "] END\n";
}

int found = true;

void dijkstra(vector<vector<int> > &adj, int n, vector<int> &path)
{
	priority_queue<pair<int, int> > q;
	vector<int> distance(n + 1, 0);
	vector<int> predecessor(n + 1, 0);
	vector<bool> processed(n + 1, false);

	distance[1] = 0;
	q.push({ 0, 1 });
	while (!q.empty()) {
		int a = q.top().second;
		q.pop();
		if (processed[a])
			continue;
		processed[a] = true;
        // deb("a: %lld, dist: %d\n", a, distance[a]);
		for (auto b : adj[a]) {
            // deb("b: %d, dist: %d\n", b, distance[b]);
			if (distance[a] + 1 > distance[b]) {
				distance[b] = distance[a] + 1;
				predecessor[b] = a;
				q.push({ distance[b], b });
			}
		}
	}

	// find shortest path
    if (predecessor[n] == 0) {
        found = false;
        return;
    }
    found = true;
    int v = n;
	while (v != 1) {
        path.push_back(predecessor[v]);
        v = predecessor[v];
	}
    reverse(path.begin(), path.end());
}

int main(int argc, char *argv[])
{
	int n, m;
	cin >> n >> m;

	// each edge is of form (a, b, c)
	vector<vector<int> > adj(n + 1, vector<int>());
    int a, b;
	for (int i = 1; i < m + 1; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
	}

    // print_matrix(adj, "adj");

    vector<int> path;
    dijkstra(adj, n, path);
    if (found) {
        cout << path.size() + 1 << "\n";
        for (auto node : path) {
            cout << node << " ";
        }
        cout << n << "\n";
    } else {
        cout << "IMPOSSIBLE";
    }

	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED