[AHOI2014/JSOI2014]骑士游戏

题目链接

问题分析

如果这个图是个DAG，那么问题就简单了。按照拓扑序的逆序做DP即可。

那么问题就在于环。于是借助SPFA的想法，更新某个节点后向它的父亲拓展，直至不能更新。

这里需要注意把可能要被更新的节点入队，而不是确定要被更新的点，否则可能TLE。具体见参考程序。

参考程序

#include <cstdio>

const int Maxn = 200010;
const int MaxR = 1000010;
int N, R, x;
long long S[Maxn], K[Maxn], s;
struct edge {
	int To, Next, Type;
	edge() {}
	edge(int _To, int _Next, int _Type) : To(_To), Next(_Next), Type(_Type) {}
};
edge Edge[MaxR << 1];
int Start[Maxn], Space;
int Head, Tail, Queue[Maxn], InQ[Maxn];
long long Dis[Maxn];

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) {
		scanf("%lld%lld", &S[i], &K[i]);
		scanf("%d", &R);
		for (int j = 1; j <= R; ++j) {
			scanf("%d", &x);
			Edge[++Space] = edge(x, Start[i], 1); Start[i] = Space;
			Edge[++Space] = edge(i, Start[x], 2); Start[x] = Space;
		}
	}
	Head = Tail = 0;
	for (int i = 1; i <= N; ++i) {
		Dis[i] = K[i];
		Queue[Tail] = i;
		++Tail; if (Tail >= Maxn) Tail = 0;
		InQ[i] = 1;
	}
	while (Head != Tail) {
		s = S[Queue[Head]];
		for (int t = Start[Queue[Head]]; t != 0; t = Edge[t].Next) {
			if (Edge[t].Type == 2) continue;
			s += Dis[Edge[t].To];
		} 
		if (s < Dis[Queue[Head]]) { //如果被更新了，就把它的所有父亲都放入队列
			Dis[Queue[Head]] = s;
			for (int t = Start[Queue[Head]]; t != 0; t = Edge[t].Next) {
				if (Edge[t].Type == 1) continue;
				if (InQ[Edge[t].To] == 1) continue;
				Queue[Tail] = Edge[t].To;
				++Tail; if (Tail >= Maxn) Tail = 0;
				InQ[Edge[t].To] = 1;
			}
		}
		InQ[Queue[Head]] = 0;
		++Head; if (Head >= Maxn) Head = 0;
	}
	printf("%lld\n", Dis[1]);
	return 0;
}