Polut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int M = 1e9 + 7;

int n, m, p, t;
vector<int> g[100001];
int dist_from_end[100001];

void find_shortest() {
    priority_queue<pair<int, int>> q;
    q.push({-1, n});
    bool vis[100001];

    while (!q.empty()) {
        pair<int, int> cur = q.top(); q.pop();

        if (vis[cur.second]) continue;
        vis[cur.second] = true;
        dist_from_end[cur.second] = -cur.first;

        for (int con : g[cur.second]) {
            q.push({cur.first - 1, con});
        }
    }
}

bool vis[100001]; // if extras == 1 and we go to an old node, return

ll dfs(int node, int steps_left) {
    if (steps_left == 0) return node == n;

    ll res = 0;
    vis[node] = true;
    for (int con : g[node]) {
        if (t <= 1 && vis[con]) continue;
        if (dist_from_end[con] > steps_left+1) continue;
        
        res += dfs(con, steps_left-1); res %= M;
    }
    vis[node] = false;
    return res;
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> p;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    find_shortest();

    for (t = 0; t < p; t++) {
        cout << dfs(1, dist_from_end[1] + t-1) << ' ';
    }

    return 0;
}

Test 1 (public)

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 4, 5

Verdict: ACCEPTED

Test 3

Group: 1, 4, 5

Verdict: ACCEPTED

Test 4

Group: 1, 4, 5

Verdict: ACCEPTED

Test 5

Group: 2, 5

Verdict: WRONG ANSWER

Test 6

Group: 2, 5

Verdict: WRONG ANSWER

Test 7

Group: 2, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3, 5

Verdict: WRONG ANSWER

Test 9

Group: 3, 5

Verdict: WRONG ANSWER

Test 10

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 5

Verdict: WRONG ANSWER

Test 14

Group: 5

Verdict: WRONG ANSWER

Test 15

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 1, 4, 5

Verdict: ACCEPTED