『图上DP·最短路』「NOIP2017」逛公园

题目描述

题解

不考虑$0$环如何处理，我们发现这和正常的最短路计数比较相似。

对于最短路计数，我们可以用$f[i]$表示到点i的最短路有多少条，在更新最短路的时候直接更新。这样的做法在实际的数据中能够拿到30分。

发现这里的$k$很小，我们可以尝试在状态上增加，即$f[i][j]$表示到第i个点，路径大小为最短路$+k$的方案数。由于更新的时候你不知道最短路，因此你必须预处理起点到每一个节点的最短路。

用Dijstra算法即可，时间复杂度：$O(nlogn)$.

考虑如何状态转移，发现很难找到一种有效的方式进行转移，我们可以使用记忆化搜索的方式进行处理，具体的，我们需要建立反向边。

我们可以在记忆化时直接调用$f(n,i),i\in [0,k].$我们求得的答案就是:$$\sum _{i=0}^{k}f[n][i]$$

对于当前的记忆化DP状态$f(i,j)$,表示在$n$到$i$的路径中，花费了比最短路多$j$的路径的长度的方案。

对于正有向边$(x,y,v)$,当前在转移状态$f(y,val)$而言；本来的路径是dis_y,如果走了这条路进行的方案就是$di{s}_x+v$,那么意味着就多花费了$t=(di{s}_x+v)?di{s}_y,$再进行对状态$f(x,val?t)$进行转移即可。

现在考虑如何处理$0$环，发现只要在记忆化的过程中，在保证每一个状态合法性(可以将不合法的预先剪枝掉)时某一个相同状态走了两遍，说明一定经过了零环。由于知道满足$val\in [0,k]$一定可以通过最短路走到起点，故一定合法；把经过零环的点和$val\in /[0,k]$的状态剪枝即可。

终于肝掉了一道毒瘤题好开心好开心~~

#include <bits/stdc++.h>using namespace std;
const int N = 300000;int n, m, k, P, tot = 0;
int Link[N], dis[N], vis[N];int f[110000][100];
int used[110000][100]; vector < pair<int,int> > a[N];struct edge {
    int y, next, v;
} e[N*2];int read(void)
{
    int s = 0, w = 0;char c = getchar();while (c < '0' || c > '9') w |= c == '-', c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}void clear(void)
{
    tot = 0;memset(f,-1,sizeof f);memset(Link,0,sizeof Link);memset(used,0,sizeof used);for (int i=0;i<N;++i) a[i].clear();
}void add(int x,int y,int v)
{
    e[++tot] = {
    y,Link[x],v};Link[x] = tot;
}void Dijkstra(void)
{
    memset(vis,0,sizeof vis);memset(dis,30,sizeof dis);priority_queue < pair<int,int> > q;q.push(make_pair(0,1)), dis[1] = 0;while (q.size()){
    int u = q.top().second;q.pop();if (vis[u]) continue;vis[u] = 1;for (int i=0;i<a[u].size();++i){
    int v = a[u][i].first;int val = a[u][i].second;if (dis[u]+val < dis[v]) {
    dis[v] = dis[u]+val;q.push(make_pair(-dis[v],v));}}}return;
}int dp(int now,int last)
{
    if (last < 0 || last > k) return 0;if (f[now][last] >= 0) return f[now][last];if (used[now][last] == 1) {
    used[now][last] = 0;return -1;}else used[now][last] = 1;int ans = 0;for (int i=Link[now];i;i=e[i].next){
    int next = e[i].y, v = e[i].v;int cost = dis[next]+v-dis[now];int val = dp(next,last-cost);if (val == -1) {
    used[now][last] = 0;return -1;}else ans = (ans+val) % P;}used[now][last] = 0;if (now == 1 && last == 0) ans = (ans + 1) % P;return f[now][last] = ans;
}int DP_work(void)
{
    int ans = 0;for (int i=0;i<=k;++i) {
    int val = dp(n,i);if (val == -1) return -1;else ans = (ans+val) % P;}return ans;
}int work(void)
{
    n = read(), m = read();k = read(), P = read();clear();for (int i=1;i<=m;++i){
    int x = read(), y = read(), v = read();add(y,x,v);a[x].push_back(make_pair(y,v));}Dijkstra();return DP_work();
}int main(void)
{
    int T = read();while (T --) printf("%d\n", work());return 0;
}