[Leaf] [P2829] 大逃离

p2829-大逃离---洛谷">P2829 大逃离 - 洛谷

1. 题面梗概

中译中：在一个无向图中，找到从 $1$ 到 $n$ 的严格次短路。

限制：除了起点和终点，所有经过的中间点，其度数（连接的边数）必须 $\ge k$。

$n \leq 5000, m \leq 100000, w \leq 10000$

2. 逻辑推导

典型的次短路问题，我们在 Dijkstra 里维护两个状态 $d_{1}$ 最短路，$d_{2}$ 次短路。

2.1 松弛

当我们通过边 $(u, v, w)$ 尝试从 $u$ 走到 $v$ 时，令新路径长度 $len = d + w$（其中 $d$ 可以是 $d1[u]$ 或 $d2[u]$）：

1. 若 $len < d1[v]$，原最短路退化为次短路，新长度上位。

2. 若 $d1[v] < len < d2[v]$，新长度更新次短路。

3. 严格处理：如果 $len == d1[v]$，由于题目要求 严格 次短路，此时不更新。

2.3 结论

这是一个典型的 “维度扩展” 思想，理论上可以维护 $k$ 短路，本题 $k = 2$。

3. 代码实现

▶

AcCode

#include<bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;

const int maxn = 5e3 + 50;
const int inf = 0x3f3f3f3f;

bool mat[maxn][maxn];
int deg[maxn];

vector<PII> adj[maxn];
int dist[maxn][2];
int n, m, k;

void dijkstra( int st )
{
    memset( dist, 0x3f, sizeof( dist ) );
    dist[1][0] = 0;

    priority_queue< PII, vector<PII>, greater<PII> > pq;
    pq.push({ 0, 1 });

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

        if( d > dist[u][1] ) continue;
        for( auto [v, w] : adj[u] )
        {
            if( v != 1 && v != n && deg[v] < k ) continue;
            int nd = d + w;

            if( nd < dist[v][0] )
            {
                if( dist[v][0] != inf )
                {
                    dist[v][1] = dist[v][0];
                    pq.push({ dist[v][1], v });
                }
                dist[v][0] = nd;
                pq.push({ dist[v][0], v });
            }
            else if( dist[v][0] < nd && nd < dist[v][1] )
            {
                dist[v][1] = nd;
                pq.push({ dist[v][1], v });
            }
        }
    }   
}

int main( )
{	
    cin >> n >> m >> k;
    for( int i = 1; i <= m; ++ i )
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
        if( !mat[u][v] )
        {
            deg[u] ++, deg[v] ++;
            mat[u][v] = mat[v][u] = 1;
        }
    }

    dijkstra( 1 );

    if( dist[n][1] == inf ) cout << -1 << '\n';
    else cout << dist[n][1] << '\n';

    return 0;
}

4. 复盘

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

• 碎碎念：这种 “状态扩展” 的思想在求 $K$ 短路或者 带限制的最短路 中非常通用。

• 关联笔记：最短路体系