自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 22:55:20，当前版本为作者最后更新于2024-02-17 19:02:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

显然点两条边不如点一条要优。题目转化为：对于任意两点 $u,v$ 满足 $u$ 能到达 $v$，求 $\min a_u+a_v$。

若图原本就有环，那么代价必定为 $0$。否则说明图 $G$ 是一个有向无环图，可以用拓扑排序维护 dp。设 $dp_u$ 表示所有能到 $u$ 的 $v$ 的 $a_v$ 的最小值，那么答案为 $\min_{(u\to v)\in E}dp_u+a_v$。

另外还要判凭空造出来一个环的情况，这时也是造二元环最优，代价为 $2(a_u+a_v)$。处理出最小值与次小值即可。时间复杂度 $O(n+m)$。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

vector<int> g[MAXN]; int d[MAXN];

int n, m, a[MAXN], dp[MAXN]; queue<int> q;

ll x, y, ans;

int main() {
	scanf("%d%d", &n, &m), x = y = 1e9;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), dp[i] = a[i];
	for (int i = 1; i <= n; i++) {
		if (a[i] <= x) y = x, x = a[i];
		else if (a[i] < y) y = a[i];
	}
	ans = x + y << 1;
	for (int i = 1, u, v; i <= m; i++) {
		scanf("%d%d", &u, &v), d[v]++;
		g[u].push_back(v);
	}
	for (int i = 1; i <= n; i++) if (!d[i]) q.push(i);
	for (int u; !q.empty(); ) {
		u = q.front(), q.pop();
		for (int v : g[u]) {
			ans = min<ll>(ans, a[v] + dp[u]), dp[v] = min(dp[v], dp[u]);
			if (!--d[v]) q.push(v);
		}
	}
	for (int i = 1; i <= n; i++) if (d[i]) ans = 0;
	printf("%lld", ans);
}