洛谷P1073题解：最短路问题的SPFA算法优化与双向边处理

一、题目解读

洛谷P1073题要求在一个有向图中，通过处理双向边和单向边，计算从起点到终点的最大利润路径。题目中包含两种边：单向边（仅允许单向通行）和双向边（可双向通行），需要利用动态规划思想结合图论算法求解最优解。

二、解题思路

采用SPFA（Shortest Path Faster Algorithm）算法，通过两次最短路径计算实现解题。首先，构建原图G和反向图rG，分别处理正向和反向的最短路径。关键在于双向边的特殊处理：若边权为2，则在正反图中均添加该边，确保双向通行性。通过两次SPFA分别计算最小代价和最大代价路径，最终取两者之差的最大值作为答案。

三、解题步骤

1. 读入节点数n、边数m及节点价格数组price。

2. 构建图结构：根据边类型（单向/双向）向G和rG添加边。

3. 运行正向SPFA（min_price数组），计算从起点1到各点的最小价格路径。

4. 运行反向SPFA（max_price数组），计算从终点n到各点的最大价格路径。

5. 遍历各节点，取max_price - min_price的最大值作为最终答案。

6. 输出结果。

四、代码与注释

#include <iostream>  

#include <vector>  

#include <queue>  

#include <algorithm>  

using namespace std;  

const int MAXN = 100010;  

const int INF = 0x3f3f3f3f;  

struct Edge {  

    int to, cost; // 边终点与权值  

};  

vector<Edge> G[MAXN], rG[MAXN]; // 正向图与反向图  

int min_price[MAXN], max_price[MAXN]; // 最小/最大路径价格  

int price[MAXN]; // 节点价格  

bool vis[MAXN]; // 节点访问标记  

// SPFA函数（is_min控制最小/最大路径计算）  

void spfa(int s, vector<Edge> graph[], int dist[], bool is_min) {  

    fill(dist, dist + MAXN, is_min? INF : -INF); // 初始化距离值  

    fill(vis, vis + MAXN, false);  

    queue<int> q;  

    dist[s] = price[s]; // 起点价格作为初始值  

    q.push(s);  

    vis[s] = true;  

    while (!q.empty()) {  

        int u = q.front(); q.pop();  

        vis[u] = false;  

        for (Edge &e : graph[u]) { // 遍历邻居节点  

            int v = e.to;  

            int new_val = is_min? min(dist[u], price[v])  : max(dist[u], price[v]);  // 根据is_min选择min或max  

            if ((is_min && new_val < dist[v]) || (!is_min && new_val > dist[v])) {  

                dist[v] = new_val; // 更新路径值  

                if (!vis[v]) {  

                    q.push(v);  

                    vis[v] = true;  

                }  

            }  

        }  

    }  

}  

int main() {  

    ios::sync_with_stdio(false);  

    cin.tie(nullptr);  

    int n, m;  

    cin >> n >> m;  

    for (int i = 1; i <= n; ++i) {  

        cin >> price[i]; // 读入节点价格  

    }  

    for (int i = 0; i < m; ++i) {  

        int x, y, z;  

        cin >> x >> y >> z;  

        G[x].push_back({y, z}); // 添加正向边  

        rG[y].push_back({x, z}); // 添加反向边  

        if (z == 2) { // 双向边特殊处理  

            G[y].push_back({x, z});  

            rG[x].push_back({y, z});  

        }  

    }  

    spfa(1, G, min_price, true); // 正向SPFA计算最小价格  

    spfa(n, rG, max_price, false); // 反向SPFA计算最大价格  

    int ans = 0;  

    for (int i = 1; i <= n; ++i) {  

        if (min_price[i]!= INF && max_price[i]!= -INF) {  

            ans = max(ans, max_price[i] - min_price[i]); // 更新最大利润  

        }  

    }  

    cout << ans << endl;  

    return 0;  

}  

五、总结

本文通过SPFA算法结合双向边处理，高效解决了洛谷P1073的最短路问题。关键在于：

1. 构建正反向图以支持双向边通行；

2. 利用min/max分支实现灵活路径计算；

3. 通过两次SPFA遍历获取最优路径差值。

该解法时间复杂度O(mn)，适用于稀疏图场景，为动态规划与图论结合的典型实例。