[Solution] 最短路题型整理

[L5] 最短路题型整理

这份笔记作为最短路的主入口，按「问题模型」而不是单纯按算法名字整理。

最短路题的主线不是“看到图就跑 Dijkstra”，而是先判断题目到底在问哪一种路径信息：
有时是普通最短路，有时是最短路条数、次短路、最短路树；有时需要把点拆成若干状态；还有一些题表面不是最短路，但可以通过固定瓶颈、固定余数、固定阶段，把问题转回最短路。

整体可以按这条线理解：

1. 基础单源最短路：求距离，同时顺手维护条数、前驱、最短路树。
2. Floyd 全源模型：点数小，或者需要“按点加入”的动态最短路。
3. 次短路模型：同一个点保留两个最优距离，路径必须严格变长。
4. 状态扩展模型：把 u 扩展成 (u, state)，用最短路处理限制和阶段。
5. 枚举瓶颈模型：固定一个限制条件后，剩下的问题变成普通最短路。
6. 同余最短路模型：把大值域压缩成余数图，求每个余数能达到的最小值。

一、基础单源最短路

这一类的常见扩展问题是最短路计数，或者最短路径相关，比如最短路树、最短路图。

Dijkstra 模板

▶

Dijkstra

// Dijkstra：适用于边权非负的单源最短路
struct Edge { int v; ll w; };
vector<Edge> adj[maxn];

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

ll dis[maxn];

void dijkstra( int S, int N ) {
    for( int i = 1; i <= N; ++ i ) dis[i] = inf;

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

    while( !pq.empty( ) ) {
        auto [u, d] = pq.top( ); pq.pop( );
        if( d > dis[u] ) continue;
        for( auto [v, w] : adj[u] ) {
            if( dis[v] > d + w ) {
                dis[v] = d + w;
                pq.push({ v, dis[v] });
            }
        }
    }
}

1. P1144 最短路计数

题意

给定一张无权无向图，求从 $1$ 到每个点的最短路条数。

思路

这题就是标准的 最短路计数 问题，自然的我们会想到用 DP 计数，当然 Dijkstra 也是一种 DP 的思想，重点在于状态转移；而这题的边权都是 1，所以可以用 BFS 代替 Dijkstra。

状态转移：

• 如果 dist < dis[v]，说明找到更短路径，直接令 cnt[v] = cnt[u]。
• 如果 dist == dis[v]，说明找到另一条同长度最短路，累加 cnt[u]。

它的本质是 “DAG 上的最短路径计数”，只是可以在 Dijkstra 松弛过程中顺手完成。

正是因为 Dijkstra 松弛的过程刚好形成了 DAG 上的转移关系。

代码部分

▶

AcCode

ll read( ) { /* 板子略 */ }

struct Edge { int v; ll w; };
vector<Edge> adj[maxn];

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

ll dis[maxn], cnt[maxn];

void dijkstra( int S, int N ) {
    for( int i = 1; i <= N; ++ i ) dis[i] = inf;
    priority_queue<State> pq;
    pq.push({ S, 0 });
    dis[S] = 0, cnt[S] = 1;
    while( !pq.empty( ) ) {
        auto [u, d] = pq.top( ); pq.pop( );
        if( d > dis[u] ) continue;
        for( auto [v, w] : adj[u] ) {
            ll dist = d + w;
            if( dist < dis[v] ) {
                dis[v] = dist;
                cnt[v] = cnt[u];
                pq.push({ v, dis[v] });
            }
            else if( dist == dis[v] ) {
                cnt[v] = ( cnt[v] + cnt[u] ) % mod;
            }
        }
    }
}

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        adj[u].push_back({ v, 1 });
        adj[v].push_back({ u, 1 });
    }
    dijkstra( 1, n );
    for( int i = 1; i <= n; ++ i ) cout << cnt[i] << '\n';
}

2. CF1076D Edge Deletion

题意

给定一张带权无向图，从 $1$ 出发，希望保留至多 $k$ 条边，使得被保留下来的点到 $1$ 的最短路距离仍然等于原图中的最短路距离，输出这些边的编号。

思路

这是一个最短路径模型的问题，一般来说，我们会在每个点第一次被松弛的时候，记录它的前驱边 pre[v]，这样就可以得到一棵从 $1$ 出发的最短路树。

当然这题也可以建一个最短路图，不过那样最后处理起来比较麻烦，可能还要倒着拓扑排序删边，而删边远没有加边简单。

题目只要求保留至多 $k$ 条边，所以从根节点开始跑一次 BFS，输出前 $k$ 条树边即可。

代码部分

▶

AcCode

ll read( ) { /* 板子略 */ }

struct Edge { int v, w, id; };
vector<Edge> adj[maxn];
struct Edge1 { int v, w; };
vector<Edge1> tadj[maxn];

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

ll dis[maxn];
PII pre[maxn]; // 分别存 { 前驱点 和 前驱边 }

void dijkstra( int S, int N ) {
    for( int i = 1; i <= N; ++ i ) dis[i] = inf;
    priority_queue<State> pq;
    pq.push({ S, 0 });
    dis[S] = 0;
    while( !pq.empty( ) ) {
        auto [u, d] = pq.top( ); pq.pop( );
        if( d > dis[u] ) continue;
        for( auto [v, w, id] : adj[u] ) {
            if( d + w < dis[v] ) {
                pre[v] = { u, id };
                dis[v] = d + w;
                pq.push({ v, dis[v] });
            }
        }
    }
}

void build( int N ) {
    for( int i = 2; i <= N; ++ i ) {
        auto [u, id] = pre[i];
        tadj[u].push_back({ i, id });
    }
}

void bfs( int S, int K ) {
    vector<int> res;
    queue<int> q;
    q.push( S );
    while( !q.empty( ) && res.size( ) < K ) {
        int u = q.front( ); q.pop( );
        for( auto [v, id] : tadj[u] ) {
            if( res.size( ) >= K ) break;
            res.push_back( id );
            q.push( v );
        }
    }
    cout << res.size( ) << '\n';
    for( int x : res ) cout << x << " ";
    cout << '\n';
}

void solve( ) {
    int n = read( ), m = read( ), k = read( );
    k = min( n - 1, k );

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( ), w = read( );
        adj[u].push_back({ v, w, i });
        adj[v].push_back({ u, w, i });
    }
    
    dijkstra( 1, n );
    build( n );
    bfs( 1, k );
}

二、Floyd 全源模型

Floyd 适合点数较小的全源最短路，它的核心思想其实是 DP，设 $dis[i][j]$ 表示当前允许经过某些中转点时，$i$ 到 $j$ 的最短路。枚举到 $k$ 时，就尝试让所有路径经过一次 $k$：

$$dis[i][j] = \min(dis[i][j], dis[i][k] + dis[k][j])$$

这个 按点加入 的结构，使 Floyd 很适合处理多阶段的问题。

Floyd 模板

▶

Floyd

// Floyd：适用于点数较小的全源最短路
ll dis[maxn][maxn];

void floyd( int n ) {
    for( int k = 1; k <= n; ++ k ) {
        for( int i = 1; i <= n; ++ i ) {
            for( int j = 1; j <= n; ++ j ) {
                if( dis[i][k] == inf || dis[k][j] == inf ) continue;
                dis[i][j] = min( dis[i][j], dis[i][k] + dis[k][j] );
            }
        }
    }
}

3. P1119 灾后重建

题意

每个村庄有一个重建完成时间，给定若干次查询，每次询问在时间 $t$ 时，两个村庄之间的最短路。

思路

这题考察了 Floyd 的 DP 本质，关键在于把 “时间” 看作阶段来处理。

由于村庄按重建时间开放，查询也按时间顺序给出，所以维护一个指针 k。每次查询时间为 $t$ 时，就把所有 a[k] <= t 的村庄加入 Floyd 中转点集合，作为一个阶段转移状态。

如果询问的起点或终点尚未重建，或者两点之间不可达，就输出 -1；否则输出当前 g[x][y]。

注：这是把一次 Floyd 拆开，随着时间这个阶段逐步完成。

代码部分

▶

AcCode

ll read( ) { /* 板子略 */ }

int a[maxn];
int g[maxn][maxn];

void solve( ) {
	int n = read( ), m = read( );
	
    for( int i = 1; i <= n; ++ i ) cin >> a[i];

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            g[i][j] = ( i == j ? 0 : inf );
        }
    }

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ) + 1, v = read( ) + 1, w = read( );
        g[u][v] = min( g[u][v], w );
        g[v][u] = min( g[v][u], w );
    }

	int q = read( );
    int k = 1;
    while( q -- ) {
        int x = read( ) + 1, y = read( ) + 1, t = read( );
        while( k <= n && a[k] <= t ) {
            for( int i = 1; i <= n; ++ i ) {
                for( int j = 1; j <= n; ++ j ) {
                    if( g[i][k] == inf || g[k][j] == inf ) continue;
                    g[i][j] = min( g[i][j], g[i][k] + g[k][j] );
                }
            }
            k ++;
        }
        if( a[x] > t || a[y] > t || g[x][y] == inf ) cout << -1 << '\n';
        else cout << g[x][y] << '\n';
    }
}

4. P6175 无向图的最小环问题

题意

给定一张无向带权图，求边权和最小的环，环中点数至少为 $3$。

思路

Floyd 的外层枚举点 $k$ 时，dis[i][j] 表示经过编号小于 $k$ 的点中转，从 $i \to j$ 的最短距离。因此在用 $k$ 更新最短路之前，枚举 $i,j<k$，就可以得到一个经过 $i,j,k$ 的环：

$$i \to k \to j \to \dots \to i$$

其中 $j \to \dots \to i$ 用的是只经过小于 $k$ 的点的最短路。于是候选答案是：

$$dis[i][j] + g[j][k] + g[k][i]$$

最后注意细节，先统计经过 $k$ 的环，再用 $k$ 更新最短路。

代码部分

▶

AcCode

ll dis[maxn][maxn];
ll g[maxn][maxn];

void solve( ) {
    int n, m;
    cin >> n >> m;

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            g[i][j] = ( i == j ? 0 : inf );
        }
    }

    for( int i = 1; i <= m; ++ i ) {
        int u, v; ll w; cin >> u >> v >> w;
        g[u][v] = min( g[u][v], w );
        g[v][u] = min( g[v][u], w );
    }
    
    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            dis[i][j] = g[i][j];
        }
    }

    ll ans = inf;
    for( int k = 1; k <= n; ++ k ) {
        for( int i = 1; i < k; ++ i ) {
            for( int j = i + 1; j < k; ++ j ) {
                ans = min( ans, dis[i][j] + g[j][k] + g[k][i] );
            }
        }
        for( int i = 1; i <= n; ++ i ) {
            for( int j = 1; j <= n; ++ j ) {
                dis[i][j] = min( dis[i][j], dis[i][k] + dis[k][j] );
            }
        }
    }
    if( ans >= inf ) cout << "No solution." << '\n';
    else cout << ans << '\n';
}

5. P2047 [NOI2007] 社交网络

题意

给定一张连通无向带权图。对每个点 $v$，计算它的重要程度，定义为：

$$I(v)=\sum_{s\ne v,t\ne v} \frac{C_{s,t}(v)}{C_{s,t}}$$

其中 $C_{s,t}$ 是 $s$ 到 $t$ 的最短路条数，$C_{s,t}(v)$ 是经过 $v$ 的最短路条数。

$n \le 100, m \le 4500$。

思路

说人话就是找到 $s \to t$ 的所有最短路中，经过 $v$ 点的比例，而既然是所有的点对，那就大概率是全源最短路的思路了，观察数据规模，也很满足 Floyd。

于是我们在维护 最短路长度 dis 的同时，也需要维护 最短路数量 cnt。

如果 $dis[s][t] = dis[s][v] + dis[v][t]$，说明 $v$ 可以处在某些 $s \to t$ 的最短路上，经过 $v$ 的最短路条数为：$C_{s,t}(v) = C_{s,v} \times C_{v,t}$。

所以最后对 $v$ 点的贡献就是：$\displaystyle \frac{C_{s,v}C_{v,t}}{C_{s,t}}$，统计所有的贡献就可以得到答案了。

注：本题枚举的是有序点对，即 $(1, 2) \neq (2, 1)$。

代码部分

▶

AcCode

ll read( ) { /* 板子略 */ }

ll dis[maxn][maxn];
ll cnt[maxn][maxn];

void solve( ) {
    int n = read( ), m = read( );

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            dis[i][j] = ( i == j ? 0 : inf );
        }
    }

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( ); 
        ll w = read( );
        dis[u][v] = dis[v][u] = w;
        cnt[u][v] = cnt[v][u] = 1;
    }

    for( int k = 1; k <= n; ++ k ) {
        for( int i = 1; i <= n; ++ i ) {
            for( int j = 1; j <= n; ++ j ) {
                if( dis[i][j] > dis[i][k] + dis[k][j] ) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                    cnt[i][j] = cnt[i][k] * cnt[k][j];
                }
                else if( dis[i][j] == dis[i][k] + dis[k][j] ) {
                    cnt[i][j] += cnt[i][k] * cnt[k][j];
                }
            }
        }
    }

    for( int k = 1; k <= n; ++ k ) {
        double ans = 0;
        for( int i = 1; i <= n; ++ i ) {
            for( int j = 1; j <= n; ++ j ) {
                if( i == j || j == k || k == i ) continue; // 事实上这句话注释也是对的
                if( cnt[i][j] && dis[i][j] == dis[i][k] + dis[k][j] ) {
                    ans += 1.0 * (cnt[i][k] * cnt[k][j]) / cnt[i][j];
                }
            }
        }
        cout << fixed << setprecision( 3 ) << ans << '\n';
    }
}

三、次短路模型

次短路字面意思就是 第二短的路径，一般来说，我们会给 dis 数组扩展一个状态，如：

• dis1[u]：到 $u$ 的最短路。
• dis2[u]：到 $u$ 的严格次短路。

所谓严格次短路，就是长度必须满足：$dis1[u] < dis2[u]$，非严格次短路就是 $dis1[u] \le dis2[u]$。

次短路模板

▶

严格次短路

// 次短路：同时维护每个点的最短路和严格次短路
ll dis1[maxn], dis2[maxn];

void dijkstra( int S, int N ) {
    for( int i = 1; i <= N; ++ i ) dis1[i] = dis2[i] = inf;

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

    while( !pq.empty( ) ) {
        auto [u, d] = pq.top( ); pq.pop( );
        if( d > dis2[u] ) continue;
        for( auto [v, w] : adj[u] ) {
            ll dist = d + w;
            if( dist < dis1[v] ) {
                dis2[v] = dis1[v];
                dis1[v] = dist;
                pq.push({ v, dist });
            }
            else if( dis1[v] < dist && dist < dis2[v] ) {
                dis2[v] = dist;
                pq.push({ v, dist });
            }
        }
    }
}

6. P2865 [USACO06NOV] Roadblocks G

题意

给定一张无向带权图，求从 $1$ 到 $n$ 的严格次短路长度。

思路

标准次短路模板题。

每次从优先队列中取出一个路径长度 d，它可能是某个点的最短路，也可能是次短路。用它继续向外扩展，如果能更新对方的最短路，就把原最短路下放成次短路；如果不能更新最短路，但介于最短路和次短路之间，就更新次短路。

代码部分

▶

AcCode

ll read( ) { /* 板子略 */ }

struct Edge { int v; ll w; };
vector<Edge> adj[maxn];

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

ll dis1[maxn], dis2[maxn];

void dijkstra( int S, int N ) {
    for( int i = 1; i <= N; ++ i ) dis1[i] = dis2[i] = inf;
    priority_queue<State> pq;
    pq.push({ S, 0 });
    dis1[S] = 0;
    while( !pq.empty( ) ) {
        auto [u, d] = pq.top( ); pq.pop( );
        if( d > dis2[u] ) continue;
        for( auto [v, w] : adj[u] ) {
            ll dist = d + w;
            if( dist < dis1[v] ) {
                dis2[v] = dis1[v];
                dis1[v] = dist;
                pq.push({ v, dist });
            } else if( dis1[v] < dist && dist < dis2[v] ) {
                dis2[v] = dist;
                pq.push({ v, dist });
            }
        }
    }
}

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        ll w = read( );
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    dijkstra( 1, n );
    cout << dis2[n] << '\n';
}

7. P2829 大逃离

题意

在图上求满足限制条件的次短路。中间点需要满足度数限制，起点和终点例外。

思路

本题是在次短路模板上加了一个“某些点能不能经过”的限制。

先预处理每个点的度数 deg[u]。在松弛边 $(u,v)$ 时，如果 $v$ 在限制条件下无法经过，那就直接跳过这个转移，限制条件体现在转移上。剩下部分就是严格次短路模板。

代码部分

▶

AcCode

ll read( ) { /* 板子略 */ }

struct Edge { int v; ll w; };
vector<Edge> adj[maxn];
int deg[maxn];
bool g[maxn][maxn];

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

ll dis1[maxn], dis2[maxn];

void dijkstra( int S, int N, int K ) {
    for( int i = 1; i <= N; ++ i ) dis1[i] = dis2[i] = inf;
    priority_queue<State> pq;
    pq.push({ S, 0 });
    dis1[S] = 0;
    while( !pq.empty( ) ) {
        auto [u, d] = pq.top( ); pq.pop( );
        if( d > dis2[u] ) continue;
        for( auto [v, w] : adj[u] ) {
            if( v != 1 && v != N && deg[v] < K ) continue;
            ll dist = d + w;
            if( dist < dis1[v] ) {
                dis2[v] = dis1[v];
                dis1[v] = dist;
                pq.push({ v, dist });
            } else if( dis1[v] < dist && dist < dis2[v] ) {
                dis2[v] = dist;
                pq.push({ v, dist });
            }
        }
    }
}

void solve( ) {
    int n = read( ), m = read( ), k = read( );
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        ll w = read( );
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
        if( !g[u][v] ) {
            g[u][v] = g[v][u] = 1;
            deg[u] ++; deg[v] ++;
        }
    }
    dijkstra( 1, n, k );
    if( dis2[n] == inf ) cout << "-1\n";
    else cout << dis2[n] << '\n';
}

四、状态扩展与分层图

这个模型的关键在于：当前在哪个点不够，还要知道当前处于什么状态。

所以把普通图上的点 $u$ 扩展成状态点：$(u, state)$

常见状态包括：用了几次免费机会、已经买没买、已经拿到哪些钥匙或剑、当前处于哪个阶段。

状态扩展模板

▶

状态扩展 Dijkstra

// 状态扩展：把「点」扩展成「点 + 状态」
// 例如 dis[u][k] 表示在 u 点，已经使用 k 次免费机会时的最短路。
ll dis[maxn][maxk];

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

void dijkstra( int S, int N, int K ) {
    for( int i = 1; i <= N; ++ i ) {
        for( int j = 0; j <= K; ++ j ) {
            dis[i][j] = inf;
        }
    }

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

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

        if( d > dis[u][k] ) continue;

        for( auto [v, w] : adj[u] ) {
            // 状态不变：正常走边
            if( dis[v][k] > d + w ) {
                dis[v][k] = d + w;
                pq.push({ v, k, dis[v][k] });
            }

            // 状态变化：使用一次特殊能力
            if( k < K && dis[v][k + 1] > d ) {
                dis[v][k + 1] = d;
                pq.push({ v, k + 1, dis[v][k + 1] });
            }
        }
    }
}

8. P4568 [JLOI2011] 飞行路线

题意

给定一张无向带权图，从 $s$ 到 $t$，最多可以让 $k$ 条边免费，求最小花费。

思路

状态设计为：dis[u][k] 表示当前在 $u$ 点，已经使用了$k$ 次免费机会时的最短路。

对于每条边 $(u,v,w)$，有且仅有两种转移：

1. 不使用免费机会：dis[v][k] = min(dis[v][k], dis[u][k] + w)。
2. 使用免费机会：dis[v][j+1] = min(dis[v][k+1], dis[u][k])，限制是免费次数没用完。

最后答案是 min(dis[t][0...k])，因为不一定要用完所有免费次数。

代码部分

▶

AcCode

ll read( ) { /* 板子略 */ }

struct Edge { int v; ll w; };
vector<Edge> adj[maxn];

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

void dijkstra( int S, int N, int K ) {
    for( int i = 1; i <= N; ++ i ) {
        for( int j = 0; j <= K; ++ j ) {
            dis[i][j] = inf;
        }
    }
    priority_queue<State> q;
    dis[S][0] = 0, q.push( { S, 0, 0 } );
    while( !q.empty( ) ) {
        auto [u, k, d] = q.top( ); q.pop( );
        if( d > dis[u][k] ) continue;
        for( auto [v, w] : adj[u] ) {
            if( k < K && dis[v][k+1] > dis[u][k] ) {
                dis[v][k+1] = dis[u][k];
                q.push({ v, k+1, dis[v][k+1] });
            } // 使用免费资格
            if( dis[v][k] > dis[u][k] + w ) {
                dis[v][k] = dis[u][k] + w;
                q.push({ v, k, dis[v][k] });
            } // 不使用免费资格
        }
    }
}

void solve( ) {
    int n = read( ), m = read( ), k = read( );
    int s = read( ) + 1, t = read( ) + 1;
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ) + 1, v = read( ) + 1;
        ll w = read( );
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    dijkstra( s, n, k );
    ll ans = inf;
    for( int j = 0; j <= k; ++ j ) ans = min( ans, dis[t][j] );
    cout << ans << '\n';
}

9. P3489 [POI2009] WIE-Hexer

题意

从 $1$ 号城镇出发到 $n$ 号城镇。某些城镇可以获得对抗怪物的剑，某些道路需要拥有对应种类的剑才能通过，求最短时间。

思路

状态设计为：dis[u][mask] 表示当前在城镇 $u$，已经拥有剑集合 mask 时的最短时间。

每条边有一个需求集合 need。只有当：( mask & need ) == need 时才能通过这条边，也就是所有需求的剑都已经获取了。到达新城镇后，立刻获得该城镇的所有剑：nxt_mask = mask | sword[v]。

这其实是一个 状态压缩 DP 的思路，所以我觉得 分层图 只是 状态扩展最短路 模型的一个特例。

代码部分

▶

AcCode

#define pb push_back
ll read( ) { /* 板子略 */ }

struct Edge { int v, w, need; };
vector<Edge> adj[maxn];

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

int dis[maxn][1 << maxp];
int sword[maxn];

void dijkstra( int S, int N, int P ) {
    for( int i = 1; i <= N; ++ i ) {
        for( int j = 0; j < ( 1 << P ); ++ j ) {
            dis[i][j] = inf;
        }
    }
    int start = sword[S];
    dis[S][start] = 0;
    priority_queue<State> pq;
    pq.push( { 0, S, start } );
    while( !pq.empty( ) ) {
        auto [d, u, mask] = pq.top( ); pq.pop( );
        if( d > dis[u][mask] ) continue;
        for( auto [v, w, need] : adj[u] ) {
            if( ( mask & need ) != need ) continue;
            int nxt_mask = mask | sword[v];
            if( dis[v][nxt_mask] > d + w ) {
                dis[v][nxt_mask] = d + w;
                pq.push({ dis[v][nxt_mask], v, nxt_mask });
            }
        }
    }
}

void solve( ) {
    int n = read( ), m = read( ), p = read( ), k = read( );

    for( int i = 1; i <= k; ++ i ) {
        int w = read( ), qi = read( );
        int mask = 0;
        for( int j = 1; j <= qi; ++ j ) {
            int rj = read( );
            mask |= ( 1 << (rj - 1) );
        }
        sword[w] |= mask;
    }

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( ), w = read( ), si = read( );
        int mask = 0;
        for( int j = 1; j <= si; ++ j ) {
            int uj = read( );
            mask |= ( 1 << (uj - 1) );
        }
        adj[u].pb( { v, w, mask } );
        adj[v].pb( { u, w, mask } );
    }

    dijkstra( 1, n, p );
    int ans = inf;
    for( int mask = 0; mask < ( 1 << p ); ++ mask ) {
        ans = min( ans, dis[n][mask] );
    }
    if( ans == inf ) cout << -1 << '\n';
    else cout << ans << '\n';
}

10. P1073 [NOIP2009 提高组] 最优贸易

题意

给定一个有向图，从 $1$ 出发到 $n$，途中最多进行一次买入和一次卖出，要求最大利润。

思路

这是一个图上的问题，简单分析后发现，每一个节点都有三种状态，还没买 | 买了没卖 | 卖了，于是就可以转化为一个 状态扩展模型 的最短路问题。

在城市 $i$ 买入，就是从第 $0$ 层走到第 $1$ 层，收益减少 $a[i]$：i -> i + n, cost = -a[i]。

在城市 $i$ 卖出，就是从第 $1$ 层走到第 $2$ 层，收益增加 $a[i]$：i + n -> i + 2 * n, cost = a[i]。

原图中的道路在三层内部都连一条权值为 $0$ 的边，最后求从 1 到 3n 求最大收益。

注1：本题和普通最短路方向相反，需要跑最长路来松弛。
注2：由于有负权边，所以考虑用 SPFA 来松弛。

代码部分

▶

AcCode

#define pb push_back
ll read( ) { /* 板子略 */ }

struct Edge { int v; ll w; };
vector<Edge> adj[maxn * 3];
int a[maxn];
ll dis[maxn * 3]; 
bool inq[maxn * 3];

void spfa( int S, int N ) {
    for( int i = 1; i <= N * 3; ++ i ) {
        dis[i] = -inf; inq[i] = 0;
    }

    queue<int> q;
    dis[S] = 0, inq[S] = true, q.push( S );
    while( !q.empty( ) ) {
        int u = q.front( ); q.pop( );
        inq[u] = false;
        for( auto [v, w] : adj[u] ) {
            if( dis[v] < dis[u] + w ) { // 最长路
                dis[v] = dis[u] + w;
                if( !inq[v] ) inq[v] = true, q.push( v );
            }
        }
    }
}

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( );
        adj[i].pb({ i + n, -a[i] });
        adj[i + n].pb({ i + 2 * n, a[i] });
    }
    for( int i = 1; i <= m; ++ i ) {
        int x = read( ), y = read( ), z = read( );
        adj[x].pb({ y, 0 });
        adj[x + n].pb({ y + n, 0 });
        adj[x + 2 * n].pb({ y + 2 * n, 0 });
        if( z == 2 ) { // 双向边的情况
            adj[y].pb({ x, 0 });
            adj[y + n].pb({ x + n, 0 });
            adj[y + 2 * n].pb({ x + 2 * n, 0 });
        }
    } 
    spfa( 1, n );
    cout << max( 0LL, dis[n * 3] ) << '\n';
}

五、同余最短路

同余最短路模型适合处理 “大值域 + 若干数任意次累加” 的问题。（这不是就是完全背包吗？）

如果直接枚举数值不可行，就选一个较小的数作为模数 mod，把所有数按照余数分组。定义：dis[r] 表示能拼出一个满足 $x \equiv r \pmod{mod}$ 的最小合法数。

只要知道了每个余数的最小可达值，就能统计区间内有多少个数可以被表示。

同余最短路模板

▶

同余最短路

// 同余最短路：dis[r] 表示能拼出余数 r 的最小数值
ll dis[maxm];
ll a[maxn];

void dijkstra( int mod, int n ) {
    for( int i = 0; i < mod; ++ i ) dis[i] = inf;

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

    while( !pq.empty( ) ) {
        auto [u, d] = pq.top( ); pq.pop( );
        if( d > dis[u] ) continue;
        for( int i = 1; i <= n; ++ i ) {
            if( a[i] == 0 ) continue;
            int v = ( u + a[i] ) % mod;
            if( dis[v] > d + a[i] ) {
                dis[v] = d + a[i];
                pq.push({ v, dis[v] });
            }
        }
    }
}

ll ask( ll x, int mod ) {
    ll res = 0;
    for( int r = 0; r < mod; ++ r ) {
        if( x >= dis[r] ) {
            res += ( x - dis[r] ) / mod + 1;
        }
    }
    return res;
}

11. P3403 跳楼机

题意

给定 $h,x,y,z$，求有多少个楼层可以通过从初始楼层不断加 $x,y,z$ 的方式到达。

思路

把问题转成：有多少个 $0 \le v \le h-1$ 可以表示成 $ax+by+cz$。

选 mod = min(x,y,z)，令 dis[r] 表示能到达余数 $r$ 的最小楼层。对于每个余数点 $i$，连边：

i -> (i + x) % mod, weight = x
i -> (i + y) % mod, weight = y
i -> (i + z) % mod, weight = z

跑完 Dijkstra 后，如果 dis[r] <= h，那么同余类 $r$ 中可达的数有：

$$\left\lfloor \frac{h - dis[r]}{mod} \right\rfloor + 1$$

代码部分

▶

AcCode

ll read( ) { /* 板子略 */ }

struct Edge { int v, w; };
vector<Edge> adj[maxn];

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

ll dis[maxn];

void dijkstra( int S, int mod ) {
    for( int i = 0; i < mod; ++ i ) dis[i] = inf;
    priority_queue<State> pq;
    pq.push({ S, 0 });
    dis[S] = 0;
    while( !pq.empty( ) ) {
        auto [u, d] = pq.top( ); pq.pop( );
        if( d > dis[u] ) continue;
        for( auto [v, w] : adj[u] ) {
            if( d + w < dis[v] ) {
                dis[v] = d + w;
                pq.push({ v, dis[v] });
            }
        }
    }
}

void solve( ) {
    ll h = read( );
    int x = read( ), y = read( ), z = read( );
    int mod = min({ x, y, z });
    h = h - 1;
    for( int i = 0; i < mod; ++ i ) {
        adj[i].push_back({ (i + x) % mod, x });
        adj[i].push_back({ (i + y) % mod, y });
        adj[i].push_back({ (i + z) % mod, z });
    }
    dijkstra( 0, mod );
    ll ans = 0;
    for( int i = 0; i < mod; ++ i ) {
        if( h >= dis[i] ) ans += 1ll * ( h - dis[i] ) / mod + 1;
    }
    cout << ans << '\n';
}

12. P2371 [国家集训队] 墨墨的等式

题意

给定 $n$ 个非负整数 $a_i$ 和区间 $[l,r]$，问有多少个 $b \in [l,r]$ 可以表示为：$\displaystyle\sum_i a_i x_i = b$，其中 $x_i$ 是非负整数。

思路

本题是上一题的更一般版本。

选所有非零 $a_i$ 中最小的作为 mod，令 dis[r] 表示能凑出余数 $r$ 的最小数。

每次使用一个 $a_i$，相当于从余数 $u$ 转移到：(u + a[i]) % mod边权为 $a[i]$。

跑完最短路后，定义 ask(x) 表示 $[0,x]$ 内能被表示的数的个数，答案就是：ask(r) - ask(l - 1)

这个模型的核心是建图，或者说是建模，关键在于把 “无限大的值域压缩成有限个余数状态”。

代码部分

▶

AcCode

ll read( ) { /* 板子略 */ }

struct Edge { int v, w; };
vector<Edge> adj[maxn];

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

ll dis[maxn];
ll a[15];

void dijkstra( int S, int mod, int N ) {
    for( int i = 0; i < mod; ++ i ) dis[i] = inf;
    priority_queue<State> pq;
    pq.push({ S, 0 });
    dis[S] = 0;
    while( !pq.empty( ) ) {
        auto [u, d] = pq.top( ); pq.pop( );
        if( d > dis[u] ) continue;
        for( int i = 1; i <= N; ++ i ) {
            if( a[i] == 0 ) continue;
            int v = (u + a[i]) % mod;
            if( d + a[i] < dis[v] ) {
                dis[v] = d + a[i];
                pq.push({ v, dis[v] });
            }
        }
    }
}

ll ask( ll x, ll mod ) {
    ll res = 0;
    for( int i = 0; i < mod; ++ i ) {
        if( x >= dis[i] ) res += 1ll * ( x - dis[i] ) / mod + 1;
    }
    return res;
}

void solve( ) {
    ll n = read( ), l = read( ), r = read( );
    ll mod = inf;
    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( );
        if( a[i] != 0 ) mod = min( mod, a[i] );
    }
    dijkstra( 0, mod, n );
    cout << ask( r, mod ) - ask( l - 1, mod ) << '\n';
}