SPFA水过，求hack

#include <cstdio>
#include <cstring>
#include <list>
#include <algorithm>
using namespace std;

#define N (10000 + 10)
#define K 100 + 10
#define inf 2139062143

struct edge_t
{
    int v, a;
};

list<edge_t> e[N];
int q[N * 100], l, r;
int f[N][K];

int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++)
    {
        int u, v, a;
        scanf("%d%d%d", &u, &v, &a);
        e[u].push_back((edge_t){v, a});
    }

    memset(f, 127, sizeof(f));
    f[1][0] = 0;
    q[r++] = 1;
    while (l < r)
    {
        int i = q[l++];
        for (auto nxt : e[i])
        {
            int j = nxt.v, a = nxt.a;
            bool flag = false;
            for (int t = 0; t < k; t++)
                if (f[i][t] != inf)
                {
                    int t2;
                    if (f[i][t] >= a)
                        t2 = f[i][t] + 1;
                    else
                        t2 = f[i][t] + (a - f[i][t]) / k * k +
                             ((a - f[i][t]) % k > 0) * k + 1;
                    if (t2 < f[j][t2 % k])
                    {
                        f[j][t2 % k] = t2;
                        flag = true;
                    }
                }
            if (flag)
                q[r++] = j;
        }
    }

    if (f[n][0] == inf)
        printf("-1\n");
    else
        printf("%d\n", f[n][0]);

    return 0;
}