UVa 10557 XYZZY

題意：
    總共有N個節點(1~N)，一開始起點在1且有100的能量，踏到每個節點都會有不同的能量變化(-100~+100)，目標是要走到終點N且過程中能量不能歸0。
想法：
    用SPFA演算法，不過要注意過程中可能會碰到正環或是負環，且有正環也不一定能走到終點，因為題目給的是單向的所以有可能走到正環的路走不到終點。因此可以假設如果走了100萬次(數字不一定)還是走不到終點就判定為無法到達。

	#include <cstdio>
	#include <queue>
	using namespace std;
	int Energy[101];
	int toNxt[101][101];
	bool SPFA(const int N);
	int main()
	{
	int N;
	while (scanf("%d", &N) && N != -1) {
	for (int i = 1; i <= N; ++i) {
	// 用toNxt[i][0]來存i能前往哪些點的數量
	scanf("%d %d", &Energy[i], &toNxt[i][0]);
	for (int j = 1; j <= toNxt[i][0]; ++j)
	scanf("%d", &toNxt[i][j]);
	}
	if (SPFA(N))
	puts("winnable");
	else
	puts("hopeless");
	}
	}
	bool SPFA(const int N)
	{
	queue<int> Q;
	int inQueue[101] = {0};
	int Dis[101] = {0};
	int Count = 0; // avoid infinite cycle
	Dis[1] = 100, inQueue[1] = true;
	Q.push(1);
	while (!Q.empty()) {
	int now = Q.front();
	inQueue[now] = false;
	Q.pop();
	for (int i = 1; i <= toNxt[now][0]; ++i) {
	int nxt = toNxt[now][i];
	int tmp = Dis[now] + Energy[nxt];
	if (tmp > Dis[nxt]) {
	Dis[nxt] = tmp;
	if (!inQueue[nxt]) {
	Q.push(nxt);
	inQueue[nxt] = true;
	++Count;
	}
	}
	}
	if (Dis[N] > 0) return true;
	if (Count > 1000000) return false;
	}
	return false;
	}

view raw [UVa] 10557 XYZZY.cpp hosted with ❤ by GitHub