P2901 [USACO08MAR] Cow Jogging G （拓扑序+归并排序）

P2901 [USACO08MAR] Cow Jogging G

拓扑序+归并排序

容易看出图是有向无环图，考虑在拓扑序上维护每个点的 \(k\) 短路。假如遍历到 \(u\)，有边 \((u,v,w)\)，\(u\)，\(v\) 各自有自己的 \(k\) 短路，我们需要将 \(u\) 上的 \(k\) 短路加 \(w\) 后与 \(v\) 上排序，然后去前 \(k\) 小。直接做是 \(O(k\log k)\) 的，但是不难想到两个有序数组可以用归并排序，这样是 \(O(k)\)。

每个边都需要合并一次，复杂度 \(O(mk)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e3 + 10;
int n, m, k;
std::vector<pii> e[N];
struct path {
	int p[110];
} a[N];
int b[N], c[N], ret[N];
void merge() {
	int bpos = 1, cpos = 1, rpos = 0;
	memset(ret, 0x3f, sizeof(ret));
	while(bpos <= k && cpos <= k) {
		if(b[bpos] <= c[cpos]) ret[++rpos] = b[bpos++];
		else ret[++rpos] = c[cpos++];
	}
	while(bpos <= k) ret[++rpos] = b[bpos++];
	while(cpos <= k) ret[++rpos] = c[cpos++];
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	std::cin >> n >> m >> k;
	for(int i = 1; i <= m; i++) {
		int u, v, d;
		std::cin >> u >> v >> d;
		e[u].pb({v, d});
	}

	std::queue<int> q;
	q.push(n);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= k; j++) a[i].p[j] = iinf;
	}
	a[n].p[1] = 0;
	for(int u = n; u >= 0; u--) {
		for(auto x : e[u]) {
			int v = x.fi, w = x.se;
			bcnt = ccnt = 0;
			for(int i = 1; i <= k; i++) b[i] = a[u].p[i] + w * (a[u].p[i] != iinf);
			for(int i = 1; i <= k; i++) c[i] = a[v].p[i];
			merge();
			for(int i = 1; i <= k; i++) a[v].p[i] = ret[i];
		}
	}

	for(int i = 1; i <= k; i++) {
		std::cout << (a[1].p[i] != iinf ? a[1].p[i] : -1) << "\n"; 
	}

	return 0;
}