OJ Board

Posted: **Sat Nov 03, 2007 3:41 pm**

Thnkx jubin for such valuble observation .

check if path[x][x] is valid. If there is a path from x, to x, then every path with x in the path is infinite.

thnkx a lot

Posted: **Mon Feb 04, 2008 6:33 pm**

Hello,

Can somebody post an input and output ?

I get WA but don't know where is the fault.

Thanks !

Posted: **Sun Jun 22, 2008 11:29 am**

Brainless wrote:Hello,

Can somebody post an input and output ?
Thanks !

I would also appreciate it if someone were able to post some IO cases, and in particular some one for which my program gives WA. I've tried with the sample IO and also with the ones I found in these forums, and in all cases my program gives the right output.

My program follows. I tried to write it in a quite readable form:

Code: Select all

<<< Removed after AC >>>
Anyway, I would still appreciate IO cases

Any help will be greatly appreciated.

Thanks,

--Dread

Posted: **Tue Aug 19, 2008 2:09 pm**

The problem text is ambiguous, so I'm posting two clarifying questions:

1:
If two streets in the input connect the same two intersections in the same direction, are they two distinct streets or just the same street stated twice?

2:
Can you double back on a two way street and call it a loop?

Example for question 1:
4
0 1 1 2 1 2 2 3
1 or 2 routes between 0 and 3?

Example for question 2:
4
0 1 1 2 2 1 2 3
How many routes from 0 to 3? 1 or infinitely many?

Snublefot

Posted: **Wed Aug 20, 2008 2:29 pm**

I guess I'll have to anser my own question:

1. They are two distinct streets yielding two distinct sets of routes.

2. No. And you can't go from one intersection to another and back again even if there are several streets between them in both directions.

Posted: **Tue Nov 11, 2008 2:26 pm**

i failed AC many times because when E=0 , i took nodes a 1 , it should nodes as 0. ie when E=0,n=0
, output is and case =10
matrix for city 10
matrix for city 11

Posted: **Thu Sep 17, 2009 8:37 pm**

Hello, guys, I need your help in problem 125. My algorithm seems to be correct and it gives right answers to all inputs known to me, but it still gets WA.

Code: Select all

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#define SIZE 35
               
int main() {

  int n, cities, step, i, j, k, c, count, curNeighbour, case_no;
  int graph_matrix[SIZE][SIZE][SIZE], sum_matrix[SIZE][SIZE];
  int neighbours [SIZE][SIZE];
  int n_counter [SIZE];
  int cycled_vertices[SIZE], good_vertices[SIZE];
  int cycled_vertices_num, good_vertices_num;
  
  case_no = -1;
  while (1) {
     if (scanf ("%d", &n) == 1) {        
        case_no++;
        
        if (n == 0) {
           printf ("matrix for city %d\n", case_no);
           continue;
        };
        
        for (i=0; i<30; i++) {
            n_counter[i] = 0;
            for (j=0; j<30; j++) {
                graph_matrix [0][i][j] = 0; 
                neighbours[i][j] = -1;
            }     
        } 
        
        cities = 0;
        for (k=0; k<n; k++) {
            scanf ("%d %d", &i, &j);
            if (i>cities)
               cities = i;
            if (j>cities)
               cities = j;            
            graph_matrix[0][i][j] = 1;
            neighbours[i][ n_counter[i] ] = j;
            n_counter[i]++;
        }
        cities++;
        
        /* Iterative DP */
        step = 1;
        for (k=0; k<cities-1; k++) {
            for (i=0; i<cities; i++)
                for (j=0; j<cities; j++) {
                     count = 0;
                     curNeighbour = 0;
                     while (neighbours[i][curNeighbour] > -1) {
                          count += graph_matrix [step-1][ neighbours[i][curNeighbour] ][j];
                          curNeighbour++; 
                     }
                     graph_matrix[step][i][j] = count;
                }
            
            step++;
        } 
        
        for (i=0; i<cities; i++)
            for (j=0; j<cities; j++) {
                count = 0;
                for (k=0; k<cities; k++)
                    count += graph_matrix[k][i][j];
                sum_matrix[i][j] = count;    
            }
        
        /* cycle detection */
        cycled_vertices_num = 0;
        good_vertices_num = 0;
        for (i=0; i<cities; i++) {
            if (sum_matrix[i][i]>0) {
               cycled_vertices[cycled_vertices_num] = i;
               cycled_vertices_num++;                     
            } else {
               good_vertices[good_vertices_num] = i;
               good_vertices_num++;                      
            }
        }
        
        /*  replacing all values for accessible vertices of cycled vertices with -1 */
        for (i=0; i<cycled_vertices_num; i++) {
            k = cycled_vertices[i];
            for (j=0; j<cities; j++)
                if (sum_matrix[k][j]>0)
                   sum_matrix[k][j] = -1;   
        }
        
        /* scanning good vertices, if good vertex has a route to a cycled vertice, all accessible points for this cycled vertice
           must be replaced with -1 in good vertex */
        for (i=0; i<good_vertices_num; i++) {
            k = good_vertices[i];
            for (j=0; j<cities; j++) {
                if (sum_matrix[k][j] > 0 && sum_matrix[j][j] < 0) {
                   for (c=0; c<cities; c++)
                       if (sum_matrix[j][c] < 0)
                          sum_matrix[k][c] = -1;                     
                }
            }    
        }
        
        printf ("matrix for city %d\n", case_no);
        for (i=0; i<cities; i++) {
            for (j=0; j<cities; j++) {
                if (j != 0)
                   printf(" ");
                printf ("%d", sum_matrix[i][j]);
            }
            printf ("\n");    
        }
                      
     } else
       break;             
  }
  
  return 0; 
}

Maybe the problem lies in invalid input handling?

Posted: **Tue Sep 17, 2013 11:51 am**

Try with

Code: Select all

return 0;

at the end of the code.

Posted: **Wed Aug 06, 2014 3:47 pm**

my code for output is:

cout<<"matrix for city "<<city<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<r[j]<<" ";
cout<<endl;
}

what is the problem?

Posted: **Wed Aug 06, 2014 4:00 pm**

You are printing extra space after last number.

Code: Select all

for(int j=0;j<n;j++)
cout<<r[i][j]<<" ";

Change it to

Code: Select all

for(int j = 0; j < n - 1; j++)
    cout<<r[i][j]<<" ";
cout<<r[i][n - 1]<<endl;

Posted: **Wed Aug 06, 2014 4:22 pm**

got AC!!
ty so much :X

Posted: **Mon Aug 11, 2014 4:47 am**

I accidentally deleted these posts:

125 numbering paths WA pl. help
Post Posted Mon Jan 19, 2004 8:37 pm by 40366

[cpp]# include<iostream>
using namespace std;
void copy(int a[][30],int b[][30],int n)
{
int i,j;
for(i = 0;i <= n;i++)
for(j = 0;j <= n;j++)
b[j] = a[j];
}
int main()
{
int m,count = 0;
while(cin >> m)
{
count++;
int i,j,k;
bool sel[30];
int a[30][30],b[30][30],c[30][30],d[30][30],e[30][30];
for(i = 0;i < 30;i++)
sel = false;
for(i = 0;i < 30;i++)
for(j = 0;j < 30;j++)
a[j] = 0;
for(i = 1;i <= m;i++)
{
cin >> j >> k;
a[j][k] = 1;
sel[j] = sel[k] = true;
}
int n;
for(i = 29;i >= 0;i--)
if(sel)
{
n = i;
break;
}
int p,q;
copy(a,b,n);
copy(b,d,n);
int x,y;
for(x = 1;x < n;x++)
{
copy(b,c,n);
for(i = 0;i <= n;i++)
{
for(j = 0;j <= n;j++)
{
int sum = 0;
for(k = 0;k <= n;k++)
sum += a[k] * c[k][j];
b[j] = sum;
}
}
for(i = 0;i <= n;i++)
for(j = 0;j <= n;j++)
d[j] += b[j];
}
copy(d,e,n);
for(x = 1;x <= m - n;x++)
{
copy(b,c,n);
for(i = 0;i <= n;i++)
{
for(j = 0;j <= n;j++)
{
int sum = 0;
for(k = 0;k <= n;k++)
sum += a[k] * c[k][j];
b[i][j] = sum;
}
}
for(i = 0;i <= n;i++)
for(j = 0;j <= n;j++)
e[i][j] += b[i][j];
}
cout << "matrix for city " << count - 1 << "\n";
for(i = 0;i <= n;i++)
{
if(d[i][0] == e[i][0])
cout << d[i][0];
else
cout << -1;
for(j = 1;j <= n;j++)
if(d[i][j] == e[i][j])
cout << " " << d[i][j];
else
cout << " " << -1;
cout << "\n";
}
}
return 0;
}[/cpp]

125 numbering paths WA pl. help
Post Posted Wed Jan 21, 2004 4:16 pm by El-idioto

Hi 40366,

Try the following input:

Code: Select all

0
3 0 1 1 2 2 1

It should return:

Code: Select all

matrix for city 0
matrix for city 1
0 -1 -1
0 -1 -1
0 -1 -1

OJ Board

125 - Numbering Paths

Re:

Clarifying questions - 125 Numbering Paths

Re: Clarifying questions - 125 Numbering Paths

Re: 125-Numbering Paths PLZ help

125 - Numbering Ways - WA

Re: 125-Numbering Paths PLZ help

125 why PE ?

Re: 125 why PE ?

Re: 125 why PE ?

Re: 125 - Numbering Paths