[NOIP2017 提高组] 逛公园 题解

题目

• $\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$ 的环，在记搜里面记录个 $e_{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 过不了（