10557 - XYZZY

[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

[deadlineruhe]

I am getting WA...
Please someone help me...

Code: Select all

AC

[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.

[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;
}

[Nuptxxp]

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

[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)

[RagingForce]

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

[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

[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]

[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.

[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;
}

[brianfry713]

Input:

Code: Select all

4
0 1 2
-100 1 3
1 1 4
0 0
-1

AC output:

Code: Select all

hopeless

[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

[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

[Mukit Chowdhury]

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