## 10557 - XYZZY

Moderator: Board moderators

danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:
I used Bellman-Ford algorithm with some modifications. Here's a sample input/output:

Input

Code: Select all

``````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
7
0 1 2
-98 2 3 5
-1 1 4
101 1 1
-60 1 6
-60 1 7
0 0
8
0 1 2
0 1 3
-5 1 4
-50 1 5
-40 2 6 7
110 1 3
0 1 8
0 0
1
0 0

7
0 2 2 6
-60 1 3
100 1 4
100 1 5
100 1 2
-120 1 7
0 0

-1``````
Output

Code: Select all

``````hopeless
hopeless
winnable
winnable
winnable
winnable
winnable
hopeless
``````
Daniel
UFRN HDD-1
Brasil

New poster
Posts: 2
Joined: Fri Sep 11, 2009 10:00 am

### Re: 10557 - XYZZY

I am getting WA...

Code: Select all

``````AC
``````

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10557 - XYZZY

I ran floyed modified and dijikstra to solve the problem. You CanT guarantee a win only if a positive cycle exists,thats the case which caused me wa.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 10557 - XYZZY

My code passed all the input found here.But still getting WA...I tried it by BFS and Floyod..Please give me some test case...

Code: Select all

``````#include<cstdio>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
#define MAXINT -1000000000
#define MAX 2000000000
typedef vector<long>vi;
queue<long>q;
long total,w,d,e,P;
bool C;
void floyod()
{
long k,i,j;
for(k=1;k<=total;k++)
for(i=1;i<=total;i++)
for(j=1;j<=total;j++)
{
if(P[i][j]<P[i][k]+P[k][j])
P[i][j]=P[i][k]+P[k][j];
C[i][j]=C[i][j]|(C[i][k]&C[k][j]);
}
}
void bfs()
{
long u,v,i;
while(!q.empty())
{
u=q.front();q.pop();
if(C[u][u]&&P[u][u]>0)
d[u]=MAX;
{
if(d[v]!=MAX&&d[v]<d[u]+w[v])
{
if(d[u]==MAX)
d[v]=MAX;
else
d[v]=d[u]+w[v];
q.push(v);
}
}
}
}
int main()
{
long a, b,j,c,i;
while(scanf("%ld",&total)==1&&total!=-1)
{
e=1;
for(i=1;i<=total;i++)
for(j=1;j<=total;j++)
{P[i][j]=MAXINT;C[i][j]=0;}
for(i=1;i<=total;i++)
{
scanf("%ld %ld",&c,&a);
w[i]=c;
for(j=1;j<=a;j++)
{
scanf("%ld",&b);
C[i][b]=1;
}
d[i]=MAXINT;
}
for(i=1;i<=total;i++)
for(j=1;j<=total;j++)
if(C[i][j])
P[i][j]=w[j];
floyod();
d=0;
q.push(1);
bfs();
d[total]+=100;
if(total==1||d[total]>0)
printf("winnable\n");
else
printf("hopeless\n");
for(i=1;i<=total;i++)
}
return 0;
}

``````

Nuptxxp
New poster
Posts: 2
Joined: Sun Dec 04, 2011 3:59 pm

### Re: 10557 - XYZZY

Could anyone tell me how to use bfs or floyd ?
i've no idea for this problem
THX

Nuptxxp
New poster
Posts: 2
Joined: Sun Dec 04, 2011 3:59 pm

### Re: 10557 - XYZZY

I got AC but i find the test date maybe is not serious
like this date:

Code: Select all

``````15
0 2 2 11
-10 1 3
-10 1 4
-10 1 5
-10 1 6
-10 1 7
-10 1 8
-10 1 9
-10 1 10
-10 1 13
50 1 12
50 1 11
11 2 10 14
-100 1 15
0 0``````
i saw a program on the web which can't pass this date but got AC
in other words,the test date don't include this states: there are two circles but the closer circle can't connect to the end room but the other do.(like my test date)
sorry for my bad english(english is not my first language)

RagingForce
New poster
Posts: 1
Joined: Fri Feb 10, 2012 5:40 pm

### Re: 10557 - XYZZY

Hi I was wondering if anyone else tried to do this problem recursively?

ze^1
New poster
Posts: 1
Joined: Mon Aug 20, 2012 12:24 pm

### Re: 10557 - XYZZY

the offical test number seems to be not completely enough?
such as this group of number. one of the AC program can't pass this correctly.

Code: Select all

``````6
0 2 2 3
1 1 4
3 2 2 4
-100 1 5
-100 1 6
0 0
-1
``````

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 10557 - XYZZY

why WA why why why????

Code: Select all

``````#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;

int main()
{
int I,K,L,M,N;
while(scanf("%d",&N)&&N>-1){
int V,D,H;
vector<int>Edge;
for(I=1;I<=N;I++){
D[I]=-1000;
H[I]=0;
}
D=100;
H=100;
for(I=1;I<=N;I++){
scanf("%d %d",&V[I],&M);
while(M--){
scanf("%d",&L);
Edge[I].push_back(L);
}
}
bool Flag=1;
for(I=1;I<=N;I++){
for(K=0;K<Edge[I].size();K++){
if(D[I]>0) Flag=0;
//printf("D[%d]=%d D[%d]=%d V[%d]=%d\n",Edge[I][K],D[Edge[I][K]],I,D[I],Edge[I][K],V[Edge[I][K]]);
if(D[Edge[I][K]]<D[I]+V[Edge[I][K]])
D[Edge[I][K]]=D[I]+V[Edge[I][K]];
// printf("D[%d]=%d D[%d]=%d V[%d]=%d\n",Edge[I][K],D[Edge[I][K]],I,D[I],Edge[I][K],V[Edge[I][K]]);

//if(H[Edge[I][K]]<H[I]+V[Edge[I][K]])
// H[Edge[I][K]]=H[I]+V[Edge[I][K]];
}
}
//printf("%d  %d\n",D[N],Flag);
for(I=1;I<=N;I++){
for(K=0;K<Edge[I].size();K++)
if(D[I]>-101&&D[Edge[I][K]]>-101&&(D[Edge[I][K]]<D[I]+V[Edge[I][K]])){
//printf("D[%d]=%d D[%d]=%d V[%d]=%d\n",Edge[I][K],D[Edge[I][K]],I,D[I],Edge[I][K],V[Edge[I][K]]);
Flag=true;
I=N+1;
break;
}
}//printf("%d  %d\n",D[N],Flag);
for(I=1;I<=N;I++){
for(K=0;K<Edge[I].size();K++)
if(D[I]>-101&&D[Edge[I][K]]>-101&&D[Edge[I][K]]>D[I]+V[Edge[I][K]]){
Flag=0;
I=N+1;
break;
}
}
//printf("%d  %d\n",D[N],Flag);
if(D[N]>0||Flag) printf("winnable\n");
else printf("hopeless\n");
}
return 0;
}

``````
[/color]
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10557 - XYZZY

After running Bellman-Ford, check for infinite energy cycles. If you can reach the exit from any of those rooms, then it's winnable.
Check input and AC output for thousands of problems on uDebug!

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

### 10557 - XYZZY WA

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

int visit;
int G;
int weight;
int to;
int dfs(int , int, int);
int bfs(int , int);
int main(void)
{
int n, i, m, k;
while(scanf("%d", &n), n != -1)
{
memset(G, 0, sizeof(G));
memset(visit, 0, sizeof(visit));
for(i = 0; i < n; i++)
{
scanf("%d", &weight[i+1]);
scanf("%d", &m);
k = 0;
while(m--)
scanf("%d", &G[i+1][k++]);
}
printf("%s\n", dfs(1, n, 100) ? "winnable" : "hopeless");
}
return 0;
}

int dfs(int x, int n, int sum)
{
int i, t, j, s;
if(x == n)
{
if(sum > 0)
return 1;
}
visit[x] = -1;
for(i = 0; G[x] != 0; i++)
{
t = G[x];
if(visit[t] == 0)
{
to[t] = x;
if(dfs(t, n, sum+weight[t]))
return 1;
}
else if(visit[t] == -1)
{
for(j = x, s = 0; j != t; j = to[j])
s += weight[j];
s += weight[t];
if(s > 0)
{
if(bfs(t, n))
return 1;
}
}
}
visit[x] = 1;
return 0;
}

int bfs(int x, int n)
{
int queue;
int V;
int first, last, i, t, temp;
first = 0;
last = 1;
queue = x;
V[x] = 1;
memset(V, 0, sizeof(V));
while(first < last)
{
temp = queue[first];
for(i = 0; G[temp] != 0; i++)
{
t = G[temp];
if(t == n)
return 1;
if(!V[t])
{
V[t] = 1;
queue[last++] = t;
}
}
first++;
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10557 - XYZZY WA

Input:

Code: Select all

``````4
0 1 2
-100 1 3
1 1 4
0 0
-1
``````
AC output:

Code: Select all

``hopeless``
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 10557 - XYZZY

A case, for which I have got the verdict WA ... :/

Code: Select all

``````7
0 1 2
-90 1 3
-90 1 4
100 1 5
100 1 6
100 3 1 4 7
0 0``````
hopeless

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### Re: 10557 - XYZZY

why getting Wrong Ans.pls help..........

Code: Select all

``````#include<iostream>
#define INF -9999999
#define MAX 10000

using namespace std;
int num_edge;

struct Edge {
public:
int start;
int des;
int weight;
};

struct Graph {
public:
int v;
Edge* edge;
};

Graph* create_Graph(int v) {
Graph* graph=new Graph();
graph->v=v;
graph->edge=new Edge[MAX];

return graph;
}

int BELLMAN_FROD(Graph* graph) {
int V=graph->v;
int E=num_edge;
int dist[V];

for(int i=1;i<=V;i++) dist[i]=INF;
dist=100;

for(int i=0;i<V;i++) {
for(int j=0;j<E;j++) {
int u=graph->edge[j].start;
int v=graph->edge[j].des;
int w=graph->edge[j].weight;

if(dist[u]!=INF && dist[v]<dist[u]+w && (dist[u]+w)>0) {
if(v==V) {
cout<<"winnable"<<endl;
return 0;
}

dist[v]=dist[u]+w;
}
}
}

int flag=0;
for(int i=0;i<E;i++) {
int u=graph->edge[i].start;
int v=graph->edge[i].des;
int w=graph->edge[i].weight;

if(dist[u]!=INF && dist[v]<dist[u]+w && (dist[u]+w)>0) {
flag=1;
break;
}
}

if(flag==1) cout<<"winnable"<<endl;
else {
if(dist[V]>0) cout<<"winnable"<<endl;
else cout<<"hopeless"<<endl;
}
}

int main()
{
int num_vertex,weight,num_doors,x;
while(1) {
cin>>num_vertex;
if(num_vertex==-1) break;
num_edge=0;
Graph* graph=create_Graph(num_vertex);

for(int i=1;i<=num_vertex;i++) {
cin>>weight;
cin>>num_doors;
for(int j=1;j<=num_doors;j++) {
cin>>x;
graph->edge[num_edge].start=i;
graph->edge[num_edge].des=x;
graph->edge[num_edge].weight=weight;
num_edge++;
}
}
BELLMAN_FROD(graph);
}
return 0;
}

``````

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 10557 - XYZZY

LazyTym wrote:why getting Wrong Ans.pls help..........

Check this case :

Code: Select all

``````6
0 1 2
5 1 3
5 2 1 4
-100 0
-100 2 4 6
0 0``````
output must be...

Code: Select all

``hopeless``