Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

UVA 10557

Autor: Lucas Castro

Código:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cassert>

using namespace std;

#define INF 0x3f3f3f3f

typedef long long int int64;
typedef long long int ll;

#define MAXN 1010

ll d[MAXN];
ll custo[MAXN];
bool vis[MAXN];
bool chega[MAXN][MAXN];
vector<int> adj[MAXN];

int cur;
void dfs(int v){
        chega[cur][v] = true;
        vis[v] = true;
        for(int i = 0 ; i < adj[v].size() ; i++){
                int pv = adj[v][i];
                if(!vis[pv]){
                        dfs(pv);
                }
        }      
}

int main(){
        int n;
        while(scanf(" %d",&n) && n != -1){
                for(int i = 0 ; i < n ; i++){
                        adj[i].clear();
                        d[i] = -INF;
                }                      

                for(int i = 0 ; i < n ; i++){
                        scanf(" %lld",&custo[i]);
                        int x;
                        scanf(" %d",&x);
                        for(int j = 0 ; j < x ; j++){
                                int a;
                                scanf(" %d",&a);
                                adj[i].push_back(a-1);
                        }                      
                }

                d[0] = 100;            
                for(int i = 0 ; i < n ; i++){
                        for(int v = 0 ; v < n ; v++){                  
                                for(int j = 0 ; j < adj[v].size() ; j++){
                                        int pv = adj[v][j];
                                        if(d[v] > 0)    d[pv] = max(d[pv],d[v] + custo[pv]);                                   
                                }                      
                        }
                }

                memset(chega,false,sizeof(chega));
                for(cur = 0 ;cur < n ; cur++){
                        memset(vis,false,sizeof(vis));
                        if(d[cur] > 0) dfs(cur);
                }              

                bool ok = d[n-1] > 0;          
                for(int i = 0 ;!ok && i < n ; i++){                                    
                        for(int j = 0 ;!ok && j < adj[i].size() ; j++){
                                int pv = adj[i][j];                            
                                if(d[pv] < d[i] + custo[pv] && chega[i][n-1]){
                                        ok = true;
                                }
                        }
                }

                if(ok) printf("winnable\n");
                else printf("hopeless\n");
        }


        return 0;
}