题目

• \(\text{30pts}\)

显然就是这道题。

• \(\text{100pts}\)

肯定要跑最短路的。令 \(d_i\) 表示 \(i\) 到 \(n\) 的最短路长度。
\(f_{u,i}\) 表示从 \(u\) 到 \(n\) 长度为 \(d_u+i\) 的路径个数。

\(dis\) 数组显然可以建反图然后跑源点为 \(n\) 的最短路。

考虑 \(f\) 数组的转移。

\[f_{u,i}=\sum{f_{v,i-(d_v+w-d_u)}} \]

其中，存在 \(u\) 到 \(v\) 的边且边权为 \(w\)。
可以这样做的原因就是 \(d_v+w-d_u\) 就是给 \(v\) 给 \(u\) 的路径距离最短路“偏差”的贡献，这样的话 \(v\) 中的偏差就必须为 \(i-(d_v+w-d_u)\)。

这样可以直接记忆化搜索也可以就跑一遍拓扑排序，我是用记搜写的。
有无数种的路线的情况就是有边权均为 \(0\) 的环，在记搜里面记录个 \(exi_{u,i}\) 数组即可，如果此时数组值为真的话就相当于找到了边权为 \(0\) 的环。

显然时间复杂度 \(O(m\log m+nk)\)。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

using LL = long long;

const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;

struct Edge {
  int to, w;
  
  Edge () {}
  Edge (int _to, int _w) { to = _to, w = _w; }
  ~Edge () {}
};

struct Node {
  int id, dis;
  
  Node () {}
  Node (int _id, int _dis) { id = _id, dis = _dis; }
  ~Node () {}
  
  friend bool operator < (const Node& n1, const Node& n2) {
    return n1.dis > n2.dis;
  }
};

vector <Edge> G[N], rG[N];
priority_queue <Node> q;

int T, n, m, k, p;
int u, v, w;
LL f[N][55], dis[N];
bool flag, vis[N], exi[N][55];

int add (int x, int y) {
  return (x + y >= p) ? (x + y - p) : (x + y);
}

void init () {
  flag = false;
  for (int i = 1; i <= n; ++i) {
    G[i].clear(), rG[i].clear();
    for (int j = 0; j <= k; ++j)
      f[i][j] = -1;
  }
  while (!q.empty())
    q.pop();
}

void AddEdge (int u, int v, int w) {
  G[u].push_back(Edge(v, w));
  rG[v].push_back(Edge(u, w));
}

void Dijkstra (int s) {
  fill(dis + 1, dis + 1 + n, INF), 
  fill(vis + 1, vis + 1 + n, false);
  q.push(Node(s, 0)), dis[s] = 0;
  while (!q.empty()) {
    Node nowtop = q.top(); q.pop();
    int nowid = nowtop.id;
    if (vis[nowid]) continue ;
    vis[nowid] = true;
    for (auto Ed : rG[nowid]) {
      int to = Ed.to, w = Ed.w;
      if (dis[to] > dis[nowid] + w) {
        dis[to] = dis[nowid] + w;
        q.push(Node(to, dis[to]));
      }
    }
  }
}

LL Solve (int x, int y) {
  if (exi[x][y]) {
    flag = true;
    return 0;
  }
  if (f[x][y] > 0)
    return f[x][y];
//  f[x][y] = 0;
  exi[x][y] = true;
  LL ret = 0;
  for (auto Ed : G[x]) {
    int to = Ed.to, w = Ed.w;
    int temp = y - (dis[to] + w - dis[x]);
    if (temp < 0 || temp > k) continue ;
    ret = add(ret, Solve(to, temp));
    if (flag) return 0;
  }
  if (x == n && !y)
    ret = 1;
  exi[x][y] = false;
  return f[x][y] = ret;
}

int main() {
  scanf("%d", &T);
  while (T--) {
    init();
    scanf("%d%d%d%d", &n, &m, &k, &p);
    for (int i = 1; i <= m; ++i) {
      scanf("%d%d%d", &u, &v, &w);
      AddEdge(u, v, w);
    }
    Dijkstra(n);
    LL res = 0;
    for (int i = 0; i <= k; ++i) {
      for (int j = 1; j <= n; ++j)
        for (int s = 0; s <= k; ++s)
          exi[j][s] = false;
      res = add(res, Solve(1, i));
    }
    printf("%lld\n", flag ? -1 : res);
  }
  return 0;
}

貌似不开 O2 过不了（