Polut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int M = 1e9 + 7;

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

int shortest_path;

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

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

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

        for (int con : g[cur.second]) {
            if (con == n) {
                shortest_path = -cur.first + 1;
                return;
            }
            q.push({cur.first - 1, con});
        }
    }
}

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

    ll res = 0;
    for (int con : g[node]) {
        res += dfs(con, steps_left-1); res %= M;
    }
    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 (int t = 0; t < p; t++) {
        cout << dfs(1, shortest_path + t) << ' ';
    }

    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: ACCEPTED

Test 6

Group: 2, 5

Verdict: ACCEPTED

Test 7

Group: 2, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3, 5

Verdict: ACCEPTED

Test 9

Group: 3, 5

Verdict: ACCEPTED

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: TIME LIMIT EXCEEDED

Test 14

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 1, 4, 5

Verdict: ACCEPTED