记忆化搜索+dijkstra

首先题目要求的是 $11$ -> $nn$ 中长度为 $dd$ ~ $d+kd+k$ 的路径条数, 通过最短路计数我们可以求出长度为 $dd$ 的路径条数, 但是无法解决 $d+1d\; +\; 1$ ~ $d+kd\; +\; k$ 的路径, 我们可以考虑一下这些路径之间的关系, $d+1d\; +\; 1$ 无非是比 $dd$ 多了 $11$, $d+kd\; +\; k$ 无非是比 $dd$ 多了 $kk$, 这些多的长度无非是分配到了某些路径上, 在某些路径上,有更短的路径, 但是它走的是更长的路径, 但是这些多走的路径长度是不能超过 $kk$ 的, 于是我们可以定义状态 $f[i,j]:f[i,j]:$ 当前点为 $ii$ 点, 并且还能够多走的路径为 $jj$, 所以最终的答案就是 $f[n][j]f[n][j]$ $(j\in [0,k])(j\in [0,k])$ 的和, 现在我们需要确定如何计算多走的路径, 我们这里还是会有一个问题, 我们多走的路径符合前提的条件下, 如何保证一定能够走到点 $nn$, 显然我们可以考虑从 $nn$ 点出发, 建反图, 求出每一个点距离 $nn$ 点的距离, 现在我们就是要求出多余的路径长度了, 我们可以看图, 多余路径的长度为: $dist[u]+w-dist[v]dist[u]\; +\; w\; -\; dist[v]$

所以我们可以通过 $dijkstradijkstra$ 预处理出距离 $nn$ 点的长度和记忆化搜索求出方案数 然后我们会发现, $WAWA$ 了!, 为什么呢, 因为我们求 $distdist$ 建的是反图, 而 $dfsdfs$ 用的是原图, 所以 $u->vu->v$ 的边, 实际上是 $vv$ -> $uu$ 的, 所以多余的路径长度应该为: $dist[v]+w-dist[u]dist[v]\; +\; w\; -\; dist[u]$

#include<bits/stdc++.h>

using namespace std;

const int N = 4e5 + 10;

typedef pair<int, int> PII;

int   ne1[N], ne2[N],  e1[N], hs[N], hr[N], e2[N], idx1, idx2,  dist[N], f[N][55], K, P, w[N], n, m;
bool st[N], vis[N][55], flag;

void add(int h[], int &idx , int ne[], int e[], int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

void dijkstra()
{
    // memset(hr, -1, sizeof hr);
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    
    dist[n] = 0;
    heap.push({0, n});
    
    while(!heap.empty())
    {
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second;
        
        if(st[ver]) continue;
        st[ver] = true;
        
        for(int i = hr[ver]; ~i; i = ne2[i])
        {
            int j = e2[i];
            if(dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}


int dfs(int u, int j)
{
    if(vis[u][j])
    {
        flag = 1;
        return 0;
    }
    
    
    if(f[u][j] != -1) return f[u][j];
    
     vis[u][j] = 1;
    int &num = f[u][j] = 0;
    for(int i = hs[u]; ~i; i = ne1[i])
    {
        int v = e1[i];
        int k = j - (dist[v] + w[i] - dist[u]);
        if(k >= 0 && k <= K) num = (num + dfs(v, k)) % P; 
        if(flag) return 0;
    }
    
    vis[u][j] = 0;
    
    if(u == n && j == 0 ) num = 1;
    return num;
}
int main()
{
    int T;
    cin >> T;
    
    while(T -- )
    {
        cin >> n >> m >> K >> P;
        
        flag = 0;
        memset(f, -1, sizeof f);
        memset(hs, -1, sizeof hs);
        memset(hr, -1, sizeof hr);
        idx1 = idx2 = 0;
        
        for(int i = 1; i <= m; i ++ )
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(hs, idx1, ne1, e1, a, b, c), add(hr, idx2, ne2, e2, b, a, c);
        }
        
        dijkstra(); 
        
    
        int ans = 0;
        for(int i = 0; i <= K; i ++ )
        {
            memset(vis, false , sizeof vis);
            ans = (ans + dfs(1, i)) % P;
            if(flag) break;
        }
        if(flag) cout << -1 << '\n';
        else cout << ans << '\n';
    }
}