给你一张\(n\)个点\(m\)条边的有向图，设从\(1\)到\(n\)的最短路为\(d\)，那么请问有多少\(1\)到\(n\)的路径（可以是非简单路径）满足其长度在\([d, d + K]\)中，如果答案为无限大的话输出\(-1\)。

\(1\leq n\leq 10^5, 1\leq m\leq 2\times 10^5, 0\leq K\leq 50\)。

UOJ疯狂卡常……搞不过去力，所以就在loj上搞了一下。

先考虑定义状态\(f_{i, j}\)表示从\(1\)到\(i\)，比两点间最短路大恰好\(j\)的边的数量，转移很显然。不过很不幸的事情是，这个DP在是有后消性的（当然如果没有零边的话没有），所以不能直接DP……然后用SPFA转移的会被卡飞……（虽说本来SPFA复杂度就不对啊）

那么我们考虑改造一下图，使得DP没后消性……我们考虑用\(p_i\)表示\(1\)到\(i\)的最短路，用\(s_i\)表示\(i\)到\(n\)的最短路，那么对于一条原图边\((u, v, w)\)，若有\(p_u + w + s_v\leq p_n + K\)的话那么留下这条边，反之则删掉。那么很显然的一件事是，图中的所有边都可能出现在一个从\(1\)到\(n\)的合法路径中，这样一来解数无穷就等价于这个新图有零环了。

然后这个DP是否就没有后消性了呢？观察到在这个图上跑DP有后消性当且仅当存在零环（因为第二维不可能变小，只可能一直不变绕回来，这样肯定就是有零环），所以只要解数有限的话那么这个图上DP就没有后消性了。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
using ll = long long;
const int maxn = 100005, maxm = 200005;
using edge = std::pair<int, int>;
struct Graph {
  std::vector<edge> *G;
  Graph() {
    G = new std::vector<edge>[maxn];
  }
  ~Graph() { delete []G; }
  void clear() {
    for(int i = 0; i < maxn; i ++) {
      G[i].clear();
    }
  }
  const std::vector<edge>& operator [](const int p) {
    return G[p];
  }
  void add_edge(int u, int v, int d) {
    G[u].push_back({v, d});
  }
};

int n, m;
using pii = std::pair<ll, int>;
inline void dij(Graph &G, int s, ll *d) {
  static bool vis[maxn]; std::fill(vis, vis + n + 2, false);
  memset(d, 0x2f, sizeof(ll) * (n + 2));
  std::priority_queue<pii, std::vector<pii>, std::greater<pii> > Q;
  d[s] = 0; Q.push({0LL, s});
  while(!Q.empty()) {
    int u = Q.top().second; Q.pop();
    if(vis[u]) continue;
    vis[u] = true;
    for(auto pr : G[u]) {
      int v = pr.first, dist = pr.second;
      if(d[u] + (ll)dist < d[v]) {
        d[v] = d[u] + (ll)dist;
        Q.push({d[v], v});
      }
    }
  }
#ifdef LOCAL
  puts("Dij ended!");
  for(int i = 1; i <= n; i ++) {
    printf("%lld ", d[i]);
  }
  puts("");
#endif
}

Graph PG, RPG, G, RG;
ll k; ll ha;
ll pd[maxn], rpd[maxn];

bool vis[maxn], ins[maxn];
int d[maxn][51];
inline bool kahn() {
  static int inv[maxn]; std::fill(inv, inv + n + 2, 0);
  for(int i = 1; i <= n; i ++) {
    for(auto e : G[i]) {
      int v = e.first;
      if(e.second == 0) {
        inv[v] ++;
      }
    }
  }
  std::queue<int> Q;
  for(int i = 1; i <= n; i ++) {
    if(inv[i] == 0) Q.push(i);
  }
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
#ifdef LOCAL
    printf("BFS %d\n", u);
#endif
    // V.push_back(u);
    for(auto e : G[u]) {
      int v = e.first;
      if(e.second == 0) {
        inv[v] --;
        if(inv[v] == 0) Q.push(v);
      }
    }
  }
  return (*std::max_element(inv + 1, inv + 1 + n)) == 0;
}
using Node = std::pair<int, int>;
int inv[maxn][51];
void dfs(int i, int j) {
  for(auto e : G[i]) {
    int v = e.first, w = e.second;
    ll nj = -pd[v] + pd[i] + (ll)j + (ll)w;
    if(nj <= k) {
      if(!inv[v][nj]) dfs(v, nj);
      inv[v][nj] ++;
    }
  }
}
inline ll solve() {
  if(!kahn()) return -1;
  for(int i = 1; i <= n; i ++) {
    for(int j = 0; j <= k; j ++) {
      inv[i][j] = 0;
    }
  }
  dfs(1, 0);
  std::queue<Node> Q; Q.push({1, 0});
  memset(d, 0, sizeof(d)); d[1][0] = 1;
  while(!Q.empty()) {
    int u = Q.front().first, j = Q.front().second; Q.pop();
#ifdef LOCAL
    printf("BFS (%d, %d)\n", u, j);
#endif
    for(auto e : G[u]) {
      int v = e.first, w = e.second;
      ll nj = -pd[v] + pd[u] + (ll)j + (ll)w;
      if(nj <= k) {
        d[v][nj] = (d[v][nj] + d[u][j]) % ha;
        inv[v][nj] --;
        if(inv[v][nj] == 0LL) Q.push({v, (int)nj});
      }
    }
  }
  ll ans = 0;
  for(int i = 0; i <= k; i ++) {
    ans += d[n][i];
    if(ans >= ha) ans -= ha;
  }
  return ans;
}

inline void readint(ll &x) {
  x = 0; char c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)) {
    x = x * 10 + (c - '0');
    c = getchar();
  }
}
inline void readint(int &x) {
  x = 0; char c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)) {
    x = x * 10 + (c - '0');
    c = getchar();
  }
}

int main() {
  int T; scanf("%d", &T);
  while(T --) {
    readint(n); readint(m); readint(k); readint(ha);
    PG.clear(); RPG.clear();
    for(int i = 1; i <= m; i ++) {
      int u, v, w;
      readint(u); readint(v); readint(w);
      PG.add_edge(u, v, w); RPG.add_edge(v, u, w);
    }
    dij(PG, 1, pd); dij(RPG, n, rpd);
    G.clear(); // RG.clear();
    for(int i = 1; i <= n; i ++) {
      for(auto e : PG[i]) {
        int v = e.first, w = e.second;
        if((pd[i] + (ll)w + rpd[v]) <= pd[n] + k) {
          G.add_edge(i, v, w); // RG.add_edge(v, u, w);
        }
      }
    }
    printf("%lld\n", solve()); fflush(stdout);
  }
  return 0;
}

• 相关文章
• 全局相关文章