HDU 1317（XYZZY）

题意：首先输入一个整数 n 代表房间数量，房间编号为 1~n；之后的 n 行是 1~n 号房间的信息，每行第 1 个数字代表此房间的能量值，第 2 个数字代表此房间能到达的房间的数量，后面的数字是此房间能到达的房间的编号。如果能从起点（1号房间）到达终点（n号房间），且能量值始终为正数，则输出"winnable"；否则输出"hopeless"。（到达终点房间时，能量值必须大于0）

由于存在负权边，所以使用 SPFA算法，详细见注释。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int n; //房间数
int mp[MAXN][MAXN]; //各房间之间的距离（出发房间的能量值）
int inQueue[MAXN]; //房间是否在队列中
int dis[MAXN]; //起点到当前房间的最短距离（最大能量值）
int time[MAXN]; //路过各房间的次数

//SPFA算法，判断起点到终点是否有路径
bool SPFA()
{
	queue<int> q;
	dis[1] = 100;
	q.push(1);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		inQueue[x] = 0;
		time[x]++;
		//某个点进入队列的次数超过n次则存在负环，在本题中表现为循环经过某一个房间，
		//能量值能够无限增加，不再向不是该环上的房间前进，所以不再将此房间入队列
		if (time[x] > n)
		{
			dis[x] = INF;
			inQueue[x] = 1;
		}
		for (int i = 1; i <= n; i++)
		{
			if (mp[x][i] != -INF && dis[i] < dis[x] + mp[x][i] && dis[x] + mp[x][i] > 0)
			{
				dis[i] = dis[x] + mp[x][i];
				if (dis[n] > 0)
					return true;
				if (inQueue[i] == 0)
				{
					inQueue[i] = 1;
					q.push(i);
				}
			}
		}
	}
	return false;
}

int main()
{
	while (cin >> n)
	{
		if (n == -1)
			break;

		memset(inQueue, 0, sizeof(inQueue));
		memset(time, 0, sizeof(time));
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
				mp[i][j] = -INF;
		}
		for (int i = 0; i <= n; i++)
		{
			dis[i] = -INF;
		}

		for (int i = 1; i <= n; i++)
		{
			int energy, num, next; //当前房间的能量，能到达房间的个数，等到达房间的编号
			cin >> energy >> num;
			for (int j = 1; j <= num; j++)
			{
				cin >> next;
				mp[i][next] = energy;
			}
		}

		if (n == 1)
		{
			cout << "winnable" << endl;
			continue;
		}
		if (SPFA() == true)
			cout << "winnable" << endl;
		else
			cout << "hopeless" << endl;
	}
	return 0;
}

继续加油。