问题概述

给定一个有向图，包含 $N$ 个节点和 $M$ 条有向边。每条边有权值 $C_i$ 表示车费，以及 $D_i$ 表示翻转该边方向的代价。我们可以选择至多翻转一条边（改变其方向但不改变车费），目标是找到从节点 $1$ 到节点 $N$ 再返回节点 $1$ 的最小总成本（车费 + 翻转代价）。

问题分析

关键观察

1. 往返路径：需要计算 $1 \rightarrow N$ 和 $N \rightarrow 1$ 两条路径的最小车费和
2. 边翻转：翻转一条边会影响两个方向的路径
3. 图规模：$N \leq 200$ 较小，$M \leq 5 \times 10^4$ 较大

算法思路

核心思想

由于 $N$ 较小，我们可以预处理多个最短路径信息，然后枚举每条可能翻转的边，快速计算翻转后的总成本。

预处理阶段

需要计算以下最短路径：

1. 原始图：

   • dist1[u]: 从 $1$ 到各点的最短距离
   • distN[u]: 从 $N$ 到各点的最短距离

2. 反向图（所有边反向）：

   • rev_dist1[u]: 在反向图中从 $1$ 到各点的最短距离（即原图中从各点到 $1$ 的距离）
   • rev_distN[u]: 在反向图中从 $N$ 到各点的最短距离（即原图中从各点到 $N$ 的距离）

枚举翻转边

对于每条边 $i = (u, v, c, d)$：

1. 不翻转该边：

   • 总成本 = dist1[N] + distN[1]

2. 翻转该边（花费 $d$ 代价）：

   • 考虑翻转后对两条路径的影响：
     • $1 \rightarrow N$ 路径：可能使用翻转后的边 $(v, u)$
     • $N \rightarrow 1$ 路径：可能使用翻转后的边 $(v, u)$

   具体计算：

   new_1_to_N = min(dist1[N], dist1[v] + c + rev_distN[u])
   new_N_to_1 = min(distN[1], distN[v] + c + rev_dist1[u])
   总成本 = new_1_to_N + new_N_to_1 + d
   

特殊情况处理

• 如果原始图中 $1$ 到 $N$ 或 $N$ 到 $1$ 不连通，且翻转边后仍不连通，则输出 $-1$
• 考虑不翻转任何边的情况

算法细节

最短路算法选择

由于 $N$ 较小但 $M$ 较大：

• 使用 Dijkstra 算法 配合堆优化
• 时间复杂度：$O(N^2 \log N)$ 或 $O(M \log N)$

图表示

• 使用邻接表存储图结构
• 分别构建原始图和反向图

边界情况

1. 重边处理：允许多条边连接相同节点
2. 零权边：$C_i$ 可能为 $0$
3. 大数值处理：$D_i$ 可达 $10^9$，注意整数溢出

复杂度分析

• 预处理：4 次 Dijkstra，$O(M \log N)$
• 枚举边：$O(M)$ 次查询，每次 $O(1)$
• 总复杂度：$O(M \log N)$，可以处理最大数据规模

实现要点

1. 初始化：正确设置无穷大值，避免溢出
2. 图构建：分别构建原始图和反向图
3. 最短路径计算：确保正确处理不连通情况
4. 答案更新：考虑所有可能情况，包括不翻转任何边

总结

本题是通过最短路预处理和枚举翻转边来解决的图论问题。关键在于预计算多个方向的最短路径信息，从而在枚举每条边时能够快速评估翻转的影响。算法充分利用了 $N$ 较小的特点，通过合理的预处理将问题简化为 $O(M)$ 的枚举过程。