Polut

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const int M = 1e9 + 7;
 
ll n, m, p, t;
vector<int> g[100001];
ll 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

map<ll, ll> cache[100001];

ll dfs(ll node, ll steps_left) {
    if (cache[node][steps_left]) return cache[node][steps_left];

    if (steps_left == 0) {
        cache[node][steps_left] = node == n;
        return node == n;
    }
 
    ll res = 0;
    vis[node] = true;
    for (ll con : g[node]) {
        if (t <= 1 && vis[con]) continue;
        //if (dist_from_end[con] > steps_left + 10) continue;
        
        res += dfs(con, steps_left-1); res %= M;
    }
    vis[node] = false;
    cache[node][steps_left] = res;
    return res;
}
 
int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
 
    cin >> n >> m >> p;
 
    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
 
    find_shortest();
 
    for (t = 0; t < p; t++) {
        //for (int i = 0; i < n; i++) cache[i].clear();

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

Test 6

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3, 5

Verdict: ACCEPTED

Test 9

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 4, 5

Verdict: ACCEPTED

Test 16

Group: 1, 4, 5

Verdict: ACCEPTED