HDU 1317 - XYZZY
传送门
题意
有N个房间,每个房间都有能量,有正有负,现在要求能否到达第n个房间,并且中途能量都为正
思路
如果存在正环,就有无限能量,这时候能到就行。用SPFA判环,如果某个点入队次数超过n,说明有正环存在。那么从起点到这个点的权就是无限大。如果最后能更新n的权,说明能到n。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#define MP(a, b) make_pair(a, b)
using namespace std;
const int MAXN = 110 + 5;
const int INF = 0x3f3f3f3f;
int mp[MAXN][MAXN], n, d[MAXN], w[MAXN];
bool SPFA()
{
queue<int> qu;
int vis[MAXN], cnt[MAXN];
memset(vis, 0, sizeof vis);
memset(cnt, 0, sizeof cnt);
d[1] = 100;
qu.push(1);
vis[1] = 1;
while (!qu.empty())
{
int t = qu.front();
qu.pop();
vis[t] = 0;
cnt[t]++;
if (cnt[t] > n)
continue;
if (cnt[t] == n)
d[t] = INF;
for (int i = 1; i <= n; i++)
{
if (mp[t][i] && d[i] < d[t] + w[i] && d[t] + w[i] > 0)
{
d[i] = d[t] + w[i];
if (i == n)
return true;
if (!vis[i])
{
qu.push(i);
vis[i] = 1;
}
}
}
}
return false;
}
int main()
{
//freopen("input.txt", "r", stdin);
int i, j, a, b, wei, nn;
while (scanf("%d", &n), n != -1)
{
memset(d, -INF, sizeof d);
memset(mp, 0, sizeof mp);
for (i = 1; i <= n; i++)
{
scanf("%d%d", &w[i], &nn);
for (j = 0; j < nn; j++)
{
scanf("%d", &a);
mp[i][a] = 1;
}
}
printf("%s\n", SPFA() ? "winnable" : "hopeless");
}
return 0;
}