5 0 1 2 -60 1 3 -60 1 4 20 1 5 0 0 5 0 1 2 20 1 3 -60 1 4 -60 1 5 0 0 5 0 1 2 21 1 3 -60 1 4 -60 1 5 0 0 5 0 1 2 20 2 1 3 -60 1 4 -60 1 5 0 0 -1
hopeless hopeless winnable winnable
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int const MAX = 105;
int n;
int w[MAX], p[MAX], cnt[MAX];
bool map[MAX][MAX], ok[MAX][MAX];
void Floyd()
{
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(!ok[i][j])
ok[i][j] = ok[i][k] && ok[k][j];
}
bool SPFA(int v0)
{
memset(p, 0, sizeof(p));
memset(cnt, 0, sizeof(cnt));
p[1] = 100;
queue <int> q;
q.push(v0);
while(!q.empty())
{
int cur = q.front();
q.pop();
cnt[cur]++;
if(cnt[cur] > n)
return ok[cur][n];
for(int i = 1; i <= n; i++)
{
if(map[cur][i] && p[i] < p[cur] + w[i])
{
q.push(i);
p[i] = p[cur] + w[i];
}
}
}
if(p[n] > 0)
return true;
return false;
}
int main()
{
while(scanf("%d", &n) != EOF && n != -1)
{
int num, v;
memset(w, 0, sizeof(w));
memset(map, false, sizeof(map));
memset(ok, false, sizeof(ok));
for(int i = 1; i <= n; i++)
{
scanf("%d %d", &w[i], &num);
for(int j = 1; j <= num; j++)
{
scanf("%d", &v);
map[i][v] = true;
ok[i][v] = true;
}
}
Floyd();
if(!ok[1][n])
printf("hopeless\n");
else
{
if(SPFA(1))
printf("winnable\n");
else
printf("hopeless\n");
}
}
}HDU 1317 XYZZY (SPFA 找正环 + Floyd 判连通)
原文:http://blog.csdn.net/tc_to_top/article/details/43710957