没有 0 边的做法

首先可以存好正图和反图。然后令 $f_{v,X}$ 表示走到 $v$，长度为 $dis_{1,v}+X$ 的路径长度。那显然可以枚举他前一个点来计算出来。这用记忆化搜索非常好写

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
const int INF = 2147483647;
int T;
int n, m, k, p;
int D; // 1~n 最短路
// 原图 e[1][~]、反图 e[0][~]
vector<pair<int, int>> e[2][MAXN + 5];
// dijkstra，起点为 s，存入 dis[now][~]
// dis[1]：1 为起点；dis[0]：n 为起点；
int dis[2][MAXN + 5];
bool vis[MAXN + 5];
priority_queue<pair<int, int>> pq;
void dijkstra(int s, int now)
{
    for (int i = 1; i <= n; i++)
    {
        dis[now][i] = INF;
        vis[i] = false;
    }
    dis[now][s] = 0;
    pq.push(make_pair(-0, s));
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < e[now][u].size(); i++)
        {
            int v = e[now][u][i].first;
            int w = e[now][u][i].second;
            if (dis[now][u] + w < dis[now][v])
            {
                dis[now][v] = dis[now][u] + w;
                pq.push(make_pair(-dis[now][v], v));
            }
        }
    }
}
// 答案 走到 v，最短路长度等于 dis[1][v]+X 的方案
int ans[MAXN + 5][55];
int dp(int v, int X)
{
    if (X < 0 || X > k)
    {
        return 0;
    }
    if (v == 1 && X == 0)
    {
        return 1;
    }
    if (ans[v][X] != -1)
    {
        return ans[v][X];
    }
    // 反图找前一个点
    int res = 0;
    int len = dis[1][v] + X;
    for (int i = 0; i < e[0][v].size(); i++)
    {
        int u = e[0][v][i].first;
        int w = e[0][v][i].second;
        // 走到前一个点，长度等于 len-w
        // dis[1][u] + ? = len - w
        res += dp(u, len - w - dis[1][u]);
        res %= p;
    }
    return ans[v][X] = res;
}
void work()
{
    // 输入
    cin >> n >> m >> k >> p;
    for (int i = 1; i <= n; i++)
    {
        e[0][i].clear();
        e[1][i].clear();
        for (int j = 0; j <= k; j++)
            ans[i][j] = -1;
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[1][u].push_back(make_pair(v, w));
        e[0][v].push_back(make_pair(u, w));
    }

    // 1 为起点的原图
    // n 为起点的反图
    // 跑出最短路
    dijkstra(1, 1);
    dijkstra(n, 0);
    D = dis[1][n]; // 1~n 最短路

    // 计算数量
    int sum = 0;
    for (int i = 0; i <= k; i++)
    {
        sum += dp(n, i);
        sum %= p;
    }
    cout << sum << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
        work();
    return 0;
}

满分做法

显然所有满足 $dis_{1,u}+dis_{u,n}\le dis_{1,n}+K$ 的点都会在某个方案中出现。所以如果这些点之间有长度为 $0$ 的环，就会出现无数方案。因此加上筛选这些点、用拓扑排序判断是否有环即可拿到满分。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
const int INF = 2147483647;
int T;
int n, m, k, p;
int D; // 1~n 最短路
// 原图1、反图0
vector<pair<int, int>> e[2][MAXN + 5];
// dijkstra，起点为 s，存入 dis[now][~]
// dis[1]：1 为起点；dis[0]：n 为起点；
int dis[2][MAXN + 5];
bool vis[MAXN + 5];
priority_queue<pair<int, int>> pq;
void dijkstra(int s, int now)
{
    for (int i = 1; i <= n; i++)
    {
        dis[now][i] = INF;
        vis[i] = false;
    }
    dis[now][s] = 0;
    pq.push(make_pair(-0, s));
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < e[now][u].size(); i++)
        {
            int v = e[now][u][i].first;
            int w = e[now][u][i].second;
            if (dis[now][u] + w < dis[now][v])
            {
                dis[now][v] = dis[now][u] + w;
                pq.push(make_pair(-dis[now][v], v));
            }
        }
    }
}
// 经过 i 号点的路径长度
int dis1n[MAXN + 5];
vector<int> eZero[MAXN + 5]; // 存所有 0 边
int inZero[MAXN + 5];        // 0 边的入度
queue<int> qZero;
// 答案 走到 v，最短路长度等于 dis[1][v]+X 的方案
int ans[MAXN + 5][55];
int dp(int v, int X)
{
    if (X < 0 || X > k)
    {
        return 0;
    }
    if (v == 1 && X == 0)
    {
        return 1;
    }
    if (ans[v][X] != -1)
    {
        return ans[v][X];
    }
    // 反图找前一个点
    int res = 0;
    int len = dis[1][v] + X;
    for (int i = 0; i < e[0][v].size(); i++)
    {
        int u = e[0][v][i].first;
        int w = e[0][v][i].second;
        // 走到前一个点，长度等于 len-w
        // dis[1][u] + ? = len - w
        res += dp(u, len - w - dis[1][u]);
        res %= p;
    }
    return ans[v][X] = res;
}
void work()
{
    // 输入
    cin >> n >> m >> k >> p;
    for (int i = 1; i <= n; i++)
    {
        e[0][i].clear();
        e[1][i].clear();
        eZero[i].clear();
        inZero[i] = 0;
        for (int j = 0; j <= k; j++)
            ans[i][j] = -1;
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[1][u].push_back(make_pair(v, w));
        e[0][v].push_back(make_pair(u, w));
        if (w == 0)
        {
            eZero[u].push_back(v);
            inZero[v]++;
        }
    }

    // 1 为起点的原图
    // n 为起点的反图
    // 跑出最短路
    dijkstra(1, 1);
    dijkstra(n, 0);
    D = dis[1][n]; // 1~n 最短路

    // 找到关键点
    // 然后在只有关键点和 0 边的图中拓扑排序看看有没有 0 环
    for (int i = 1; i <= n; i++)
    {
        dis1n[i] = dis[1][i] + dis[0][i];
        // 去掉无关点的出边
        if (dis1n[i] > D + k)
        {
            inZero[i] = 0;
            for (int ii : eZero[i])
                inZero[ii]--;
        }
    }
    for (int i = 1; i <= n; i++)
        if (dis1n[i] <= D + k &&
            inZero[i] == 0)
        {
            qZero.push(i);
        }
    while (!qZero.empty())
    {
        int u = qZero.front();
        qZero.pop();
        for (int v : eZero[u])
        {
            if (dis1n[v] > D + k)
                continue;
            inZero[v]--;
            if (inZero[v] == 0)
                qZero.push(v);
        }
    }
    for (int i = 1; i <= n; i++)
        if (dis1n[i] <= D + k &&
            inZero[i] != 0)
        {
            cout << -1 << "\n";
            return;
        }

    // 计算数量
    int sum = 0;
    for (int i = 0; i <= k; i++)
    {
        sum += dp(n, i);
        sum %= p;
    }
    cout << sum << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
        work();
    return 0;
}