OJ Board

The Online Judge board
https://onlinejudge.org/board/

10557 - XYZZY

https://onlinejudge.org/board/viewtopic.php?t=4056

Page 2 of 3

Posted: Mon Oct 31, 2005 8:39 pm
by danielrocha
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

Re: 10557 - XYZZY

Posted: Sat Nov 13, 2010 11:16 am
by deadlineruhe
I am getting WA...
Please someone help me...

Code: Select all

AC

Re: 10557 - XYZZY

Posted: Fri May 06, 2011 10:46 pm
by Shafaet_du
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.

Re: 10557 - XYZZY

Posted: Wed May 18, 2011 10:30 am
by Imti
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;
vi adj[120],cost[120];
queue<long>q;  
long total,w[120],d[120],e,P[120][120];
bool C[120][120];
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;
       for(i=0;i<adj[u].size();i++)
       {
         v=adj[u][i];
         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);
       adj[i].push_back(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[1]=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++)
      adj[i].clear();
  }
  return 0;
}

Re: 10557 - XYZZY

Posted: Sun Dec 04, 2011 4:07 pm
by Nuptxxp
Could anyone tell me how to use bfs or floyd ?
i've no idea for this problem
THX

Re: 10557 - XYZZY

Posted: Tue Dec 06, 2011 9:54 am
by Nuptxxp
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)

Re: 10557 - XYZZY

Posted: Fri Feb 10, 2012 7:23 pm
by RagingForce
Hi I was wondering if anyone else tried to do this problem recursively?

Re: 10557 - XYZZY

Posted: Mon Aug 20, 2012 12:36 pm
by ze^1
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

Re: 10557 - XYZZY

Posted: Tue Jul 02, 2013 11:22 pm
by mahade hasan
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[110],D[110],H[110];
        vector<int>Edge[110];
        for(I=1;I<=N;I++){
            D[I]=-1000;
            H[I]=0;
        }
        D[1]=100;
        H[1]=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]

Re: 10557 - XYZZY

Posted: Thu Jul 04, 2013 1:31 am
by brianfry713
After running Bellman-Ford, check for infinite energy cycles. If you can reach the exit from any of those rooms, then it's winnable.

10557 - XYZZY WA

Posted: Mon Aug 05, 2013 11:39 am
by hpjhc
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

int visit[101];
int G[101][101];
int weight[101];
int to[101];
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[101];
int V[101];
int first, last, i, t, temp;
first = 0;
last = 1;
queue[0] = 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;
}

Re: 10557 - XYZZY WA

Posted: Wed Aug 07, 2013 12:19 am
by brianfry713
Input:

Code: Select all

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

Code: Select all

hopeless

Re: 10557 - XYZZY

Posted: Wed Aug 06, 2014 12:04 pm
by Mukit Chowdhury
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
answer must be
hopeless

Re: 10557 - XYZZY

Posted: Mon Oct 13, 2014 9:30 pm
by LazyTym
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[1]=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;
}
thanks in Advanced

Re: 10557 - XYZZY

Posted: Tue Oct 14, 2014 7:31 am
by Mukit Chowdhury
LazyTym wrote:why getting Wrong Ans.pls help..........
thanks in Advanced

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
All times are UTC+02:00
Page 2 of 3

Powered by phpBB® Forum Software © phpBB Limited