洛谷题单指南-树与图上的动态规划-P3953 [NOIP 2017 提高组] 逛公园

原题链接：https://www.luogu.com.cn/problem/P3953

题意解读：设dist[n]表示1到n的最短路径，求1~n的所有路径中长度不超过dist[n] + k的条数。

解题思路：

由于k的范围0~50，可以考虑枚举所有路径长度的数量：dist[n]、dist[n]+1、dist[n]+2……

对于某一种路径长度的路线数量怎么求？如果没有环，直接通过拓扑序来DP就可以。

但是有环，因为0环才会导致路线有无数条！

可以用记忆化搜索的方式来DP。

1、先通过Dijikstra计算最短路

2、枚举所有的dist[n]+k

  设f[u][y]表示从1到u路径长度是dist[u]+y的路线条数

  假设有v1、v2、v3…到u有边，建图时考虑建反向边，这样对于所有u->v

  设f[v][x]使从1到v的路径长度是dist[v]+x的路线条数，又有dist[v]+x+w[u->v] = dist[u]+y，因此x=dist[u]+y-dist[v]-w[u->v]

  如此则有状态转移：f[u][y] += ∑ f[v][dist[u]+y-dist[v]-w[u->v]]

3、通过记忆化搜索来求dp(u, y)，初始值f[1][0] = 1

4、用bool vis2[u][y]记录搜索过程中在栈中的节点（dfs开始时置true、回溯时置false，这样回溯之前如果碰到true说明还在递归栈中，重复了），如果重复搜索，则表示存在环，且一定是0环，因为不是0环会导致路径边长，不可能在最短路形成的拓扑图中。

5、这里DFS的本质就是按照最短路的拓扑序DP的过程

6、建图时，用链式前向星建双向边，idx奇数是正向边，偶数是反向边

100分代码：

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 100005, M = 400005, K = 55;
int head[N], to[M], w[M], nxt[M], idx;
int dist[N];
bool vis[N];
int f[N][K]; //f[u][y]表示从1到u的路径长度是dist[u]+y的路线条数
bool vis2[N][K]; //vis2[u][y]表示在递归时，是否访问过节点u和路径长度y
bool flag; //是否存在环
int t, n, m, k, p;

void add(int a, int b, int c)
{
    to[++idx] = b;
    w[idx] = c;
    nxt[idx] = head[a];
    head[a] = idx;
}

void dijikstra()
{
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, 1});
    while(pq.size())
    {
        PII item = pq.top(); pq.pop();
        int u = item.second;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = head[u]; ~i; i = nxt[i])
        {
            if(i % 2 == 0) continue; //只考虑正向边
            int v = to[i];
            if(dist[v] > dist[u] + w[i])
            {
                dist[v] = dist[u] + w[i];
                pq.push({dist[v], v});
            }
        }
    }
}

int dp(int u, int y)
{
    //存在环，dfs到重复节点
    if(vis2[u][y])
    {
        flag = true;
        return 0;
    }

    //如果已经计算过，直接返回
    if(f[u][y] != -1) return f[u][y];

    vis2[u][y] = true; //标记当前节点和路径长度

    f[u][y] = 0; //初始化当前状态的路径条数为0
    for(int i = head[u]; ~i; i = nxt[i])
    {
        if(i % 2 == 1) continue; //只考虑反向边
        int v = to[i];
        int x = dist[u] - dist[v] + y - w[i];
        if(x < 0 || x > k) continue; //如果x不在[0, k]范围内，跳过
        f[u][y] = (f[u][y] + dp(v, x)) % p; //递归计算
        if(flag) break;
    }
    if(u == 1 && y == 0)  f[u][y] = 1; //从1到1的路径长度为0的路线条数为1
    vis2[u][y] = false; //回溯
    return f[u][y];
}

int main()
{
    cin >> t;

    while(t--)
    {
        memset(head, -1, sizeof(head));
        idx = 0;
        cin >> n >> m >> k >> p;
        while(m--)
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c), add(b, a, c); //双向边
        }
        dijikstra();

        memset(f, -1, sizeof(f));
        memset(vis2, false, sizeof(vis));
        flag = false;
        int ans = 0;
        for(int i = 0; i <= k; i++)
        {
            ans = (ans + dp(n, i)) % p; //计算从1到n的路径条数
            if(flag) break; //如果存在环，跳出循环
        }
        if(flag) ans = -1;
        cout << ans << endl;
    }
    return 0;
}