HDU 1317 XYZZY Bellman - ford 최 장 로 판단 정 환 구하 기

제목: n 개의 방 을 드 리 겠 습 니 다. 에너지 100 으로 1 부터 n 번 째 방 까지 판단 할 수 있 습 니 다.
한 방 에 도착 할 때마다 에너지 x 를 얻 을 수 있 습 니 다 (0 보다 작 을 수 있 습 니 다)  한 방 에 도착 할 때마다 총 에 너 지 는 0 이상 이 어야 한다. 방 마다 반복 해서 도착 할 수 있다.
사고방식: 1 에서 n 까지 의 가장 긴 길 을 구하 지만 정 환 이 정 환 이 없 으 면 가장 긴 길 을 직접 구 할 수 있 습 니 다. 만약 에 정 환 이 있 으 면 링 중의 점 이 n 에 도달 할 수 있 는 지 판단 할 수 있 습 니 다.
구체 적 으로 Bellman - ford 알고리즘 을 사용 하면 복잡 도 는 (n * m) 이지 만 이 문 제 는 괜 찮 을 것 같 습 니 다.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 110;
struct edge
{
	int u, v, w;
};

vector <edge> G;
int dis[maxn];
bool vis[maxn];
int n, m;
int a[maxn][maxn];
void floyd()
{
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				a[i][j] = a[i][j] || (a[i][k] && a[k][j]);
		
}
bool Bellman_Ford()
{
	for(int i = 1; i <= n; i++)
		dis[i] = -999999999;
	dis[1] = 100;
	for(int i = 1; i < n; i++)
	{
		for(int j = 0; j < G.size(); j++)
		{
			edge e = G[j];
			if(dis[e.v] < dis[e.u] + e.w && dis[e.u] + e.w > 0)
				dis[e.v] = dis[e.u] + e.w;	
		}
	}
	//printf("%d
", dis[n]);
	if(dis[n] > 0)
		return true;
	for(int i = 0; i < G.size(); i++)
	{
		edge e = G[i];
		if(dis[e.v] < dis[e.u] + e.w && dis[e.u] + e.w > 0)
		{
			//puts("sss");
			dis[e.v] = dis[e.u] + e.w;	
			if(a[e.v][n])
				return true;
		}
	}
	return false;
}
int main()
{
	
	while(scanf("%d", &n) && n != -1)
	{
		//for(int i = 0; i <= n; i++)
		G.clear();
		memset(a, 0, sizeof(a));
		for(int i = 1; i <= n; i++)
		{
			int t, v, w;
			scanf("%d %d", &w, &t);
			while(t--)
			{
				scanf("%d", &v);
				G.push_back((edge){i, v, w});
				//G.push_back((edge){v, i, w});
				a[i][v] = 1;
				//a[v][i] = 1;
				//G[v].push_back((edge){u, w});
			}
		}
		floyd();
		if(Bellman_Ford())
			puts("winnable");
		else
			puts("hopeless");
	}
	return 0;
}