[Leaf] [P3953] 逛公园

p3953-[noip-2017-提高组]-逛公园---洛谷">P3953 [NOIP 2017 提高组] 逛公园 - 洛谷

1. 题面梗概

中译中：给出一张 $n$ 个点 $m$ 条边的有向图。设 $1 \to n$ 的最短路长度为 $d$。求 $1 \to n$ 长度不超过 $d + K$ 的路径总数。若存在 0 环导致路径无限，输出 -1。

$n \le 10^5, m \le 2 \cdot 10^5, K \le 50, w_i \in [0, 1000]$

2. 逻辑推导

首先肯定是考虑最短路，直接上 dijkstra 跑一个单源最短路出来，然后用 DP 转移计数，这题应该就解决了。

求最短路就略了，模板。

2.1 状态设计

题目要求的路径长度 $d \leq L \leq d + K$。由于 $K \leq 50$，我们可以将它作为一种状态扩展。

定义 “剩余距离” 为 $\Delta = L - dist(1, u)$。对于每一条边 $( u, v, w )$，它对 “剩余距离” 的消耗量为：

$$cost = w - ( dist(1, v) - dist(1, u))$$

2.2 记忆化搜素

我们定义 $dp[u][k]$ 为 $1 \to u$，且当前路径比 $dist[u]$ 恰好大 $k$ 的方案数。

状态转移：考虑反向转移，对于边 $v \xrightarrow{w} u$，如果我们要计算 $dp[u][k]$，则前驱状态必须满足：

$$(dist(1, v) + k_{prev}) + w = dist(1, u) + k$$

推导出：

$$k_{prev} = k - (dist(1, v) + w - dist(1, u))$$

只要 $k_{prev} \ge 0$，该转移即合法。

2.3 0 环判定

如果图中存在边权为 $0$ 的边，且这些边构成了环，且环位于某条长度 $\leq d + K$ 的路径上，则会有无数种方案。

在记忆化搜素中，我们可以利用 $vis[u][k]$ 数组，如果二次访问到了 $(u, k)$ 就说明存在 $0$ 环。

只有消耗量为 0 的边才会导致 $k$ 不变，从而在 DFS 过程中触发 vis 标记。

3. 代码实现

▶

AcCode

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

const int maxn = 2e5 + 5;
const ll inf = 1e18;

struct Edge { int v, w; };
vector< Edge > adj[maxn], radj[maxn];
bool vis[maxn][55];
ll dp[maxn][55];
// dp[u][k] 表示 1 -> u 路径上，距离为 disy[u] + k 的方案数
ll dist[maxn];
int n, m;
ll K, P;
bool cycle;

struct State {
    int u; ll d;
    bool operator < ( const State &oth ) const { return d > oth.d; }
};

void dijkstra( )
{
    for( int i = 1; i <= n; ++ i ) dist[i] = inf;
    dist[1] = 0;

    priority_queue< State > pq;
    pq.push({ 1, 0 });

    while( !pq.empty( ) )
    {
        auto [u, d] = pq.top( ); pq.pop( );
        if( d > dist[u] ) continue;

        for( auto [v, w] : adj[u] )
        {
            if( dist[v] > dist[u] + w )
            {
                dist[v] = dist[u] + w;
                pq.push({ v, dist[v] });
            }
        }
    }
}

ll dfs( ll u, ll k )
{
    if( k < 0 || k > K ) return 0;
    if( vis[u][k] ) 
    {
        cycle = true;
        return 0;
    }
    if( dp[u][k] != -1 ) return dp[u][k];

    vis[u][k] = true;
    ll res = 0;
    if( u == 1 && k == 0 ) res = 1;
    
    for( auto [v, w] : radj[u] )
    {
        ll nk = k - ( dist[v] + w - dist[u] );
        res = ( res + dfs( v, nk ) ) % P;
        if( cycle ) return 0;
    }

    vis[u][k] = false;
    return dp[u][k] = res;
}

void solve( )
{
    cin >> n >> m >> K >> P;

    for( int i = 1; i <= n; ++ i )
    {
        adj[i].clear( );
        radj[i].clear( );
    }
    
    for( int i = 1; i <= m; ++ i )
    {
        int u, v, w; 
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
        radj[v].push_back({ u, w });
    }

    dijkstra( );
    memset( vis, 0, sizeof( vis ) );
    memset( dp, -1, sizeof( dp ) );
    cycle = false;

    ll ans = 0;
    for( int i = 0; i <= K; ++ i )
    {
        ans = ( ans + dfs( n, i ) ) % P;
        if( cycle )
        {
            cout << -1 << '\n';
            return;
        }
    }
    cout << ans << '\n';
}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _t = 1;
    cin >> _t;
    while( _t -- ) solve( );
    return 0;
}

4. 复盘

• 复杂度分析：$O( T \cdot ( M \log N + N \cdot K ) )$。

• 碎碎念：图上扩展状态，关于路径的计数DP。

• 关联笔记：树图DP | 最短路体系