[Leaf] [P9751] 旅游巴士

p9751-[csp-j-2023]-旅游巴士---洛谷">P9751 [CSP-J 2023] 旅游巴士 - 洛谷

1. 题面梗概

中译中: 每条路有开启时间 $a_i$。出发和到达时间必须是 $k$ 的倍数。求最快到达时间。

2. 逻辑推导

如果忽略掉每条路的开启时间 $a_i$，这就是个关于 $k$ 的同余最短路问题。但考虑到 $a_i$，我们可能需要原地等待一段时间。

2.1 同余系

如果你在 $t$ 时刻到达 $u$，由于出发时间必须是 $k$ 的倍数，且路上耗时固定，那么到达每个点的时刻 $t \pmod k$ 是固定的。

因此，如果在时刻 $t$ 到达 $u$，且边 $(u, v)$ 没开 $(t < a_i)$，那么我们就需要在出发点多等几个 $k$。

而这意味着整体时间轴向后平移，但余数 $t \pmod k$ 是不变的。

2.2 状态扩展

定义：$dp[u][rem]$ 表示到达 $u$，且时刻 $t \pmod k = rem$ 的最小时间。

转移时，如果当前时刻 $t < a_i$，则多等一会 $wait = \lceil \frac{a_i - t}{k} \rceil \times k$，

这个向上取整的柿子，可以转化为 wait = ( a[i] - t + k - 1 ) / k * k;。

接着在这个状态图上跑一遍 $Dijkstra$ 即可。

3. 代码实现

▶

AcCode

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

const int maxn = 1e4 + 5;
const int maxk = 100 + 5;
const ll inf = 1e18;

struct Edge { int v, a; };

vector< Edge > adj[maxn];

ll dp[maxn][maxk];
bool vis[maxn][maxk];
int n, m, k;

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

void bfs( )
{
    for( int i = 1; i <= n; ++ i )
    {
        for( int j = 0; j <= k; ++ j )
        {
            dp[i][j] = inf;
        }
    }

    priority_queue< State > q;
    
    q.push({ 1, 0 });
    dp[1][0] = 0;
    
    while( !q.empty( ) )
    {
        auto [u, t] = q.top( );
        q.pop( );

        if( vis[u][t % k] ) continue;
        vis[u][t % k] = true;

        for( auto& [v, a] : adj[u] )
        {
            int wait = 0;
            if( t < a ) wait = ( a - t + k - 1 ) / k * k;
            int nt = t + wait + 1;
            if( nt < dp[v][nt % k] )
            {
                dp[v][nt % k] = nt;
                q.push({ v, nt });
            }
        }
    }
}


void solve( )
{
    cin >> n >> m >> k;

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

    bfs( );

    if( dp[n][0] == inf ) cout << "-1" << "\n";
    else cout << dp[n][0] << "\n";
}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve( );
    return 0;
}

4. 复盘

• 复杂度分析：$O( kM \log (kN) )$。

• 碎碎念：这题的状态设计非常巧，虽然看上去像同余最短路，但其核关键在于延迟的等待时间。`

• 关联笔记：最短路体系