[Leaf] [P4568] 飞行路线

p4568-[jloi2011]-飞行路线---洛谷">P4568 [JLOI2011] 飞行路线 - 洛谷

1. 题面梗概

中译中: 给一张带权图，你有 $k$ 次机会让某条边的权值归零。求 $s$ 到 $t$ 的最短路。

2. 逻辑推导

如果没有 $k$ 次免费机会，就是单纯的 Dijkstra。由于 $k$ 的规模很小（ $k \le 10$ ），这暗示我们可以通过增加维度来处理这个有限资源约束。

2.1 分层图

我们关注的状态有两个：一个是到了哪里，另一个是用了几次免费机会。

因此我们可以考虑分层图解决问题，建立 $k + 1$ 层图，第 $i$ 层代表已经使用了 $i$ 次免费机会。

如此，每次转移有两种情况，使用免费机会和不使用免费机会。

• 不使用：在同一层内移动，花费原价，即 $(u, j) \to (v, j)$。

• 使用：从第 $j$ 层向第 $j+1$ 层移动，花费为 0。即 $(u, j) \to (v, j+1)$。

最终在扩展后的状态空间上跑一遍 Dijkstra 即可。

2.2 结论

分层图最短路 经典例题。

3. 代码实现

▶

AcCode

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

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

struct Edge { int v, w; };
vector< Edge > adj[maxn];
ll dist[maxn][maxk];
bool vis[maxn][maxk];
int n, m, k, s, t;

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

void dijkstra( int s )
{
    for( int i = 1; i <= n; ++ i )
    {
        for( int j = 0; j <= k; ++ j )
        {
            dist[i][j] = inf;
            vis[i][j] = false;
        }
    }

    priority_queue< State > pq;
    pq.push({ s, 0, 0 });
    dist[s][0] = 0;

    while( !pq.empty( ) ) 
    {
        auto [u, nk, d] = pq.top( );
        pq.pop( );

        if( vis[u][nk] ) continue;
        vis[u][nk] = true;

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

void solve( )
{
    cin >> n >> m >> k >> s >> t;
    s ++, t ++;
    for( int i = 1; i <= m; ++ i ) 
    {
        int u, v, w;
        cin >> u >> v >> w;
        u ++, v ++;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }

    dijkstra( s );

    ll ans = inf;
    for( int i = 0; i <= k; ++ i ) ans = min( ans, dist[t][i] );
    cout << ans << '\n';
}

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

4. 复盘

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

• 碎碎念：分层图最短路典例。层的本质是对状态的扩展。最后答案要对所有层 dist[t][j] 取最小值，因为到达终点时不一定非要用完所有免费额度。

• 关联笔记：最短路体系