567 - Risk

[sapnil]

To alamgir

-> You should print a blank line after each case
-> Remove the line
freopen("output.txt","w", stdout);
freopen("input.txt","r", stdin);

Thanks
Keep posting
Sapnil

[turcse143]

thanks a lot man.
i got AC by using BFS.

[theharshest]

Please help.. I am getting WA

Code: Select all

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

int main()
{
	int g[25][25][25];
	int t,m,c=0,x,y,n;
	
	while(1)
	{
	c++;
	for(int i=0;i<20;i++)
		for(int j=0;j<20;j++)
			{
				if(i!=j)
					g[0][i][j]=1000;
				else
					g[0][i][j]=0;
			}

	for(int i=0;i<19;i++)
	{
			
			
			if(cin>>t)
			for(int j=0;j<t;j++)
			{
				cin>>m;
				g[0][i][m-1]=1;
				g[0][m-1][i]=1;
			}
			else
			goto end;
	}
		
	for(int k=1;k<20;k++)
		for(int i=0;i<20;i++)
			for(int j=0;j<20;j++)
				g[k][i][j]=min(g[k-1][i][j] , g[k-1][i][k] + g[k-1][k][j]);

	cin>>n;

	cout<<"Test Set #"<<c<<endl;
	for(int i=0;i<n;i++)
	{
		cin>>x>>y;
		printf("%2d to %2d: %d\n",x,y,g[19][x-1][y-1]);
	}
	
	cout<<endl;	

	}
	end:;

}

[dodouuu]

I got wrong answer, too

can anyone give me some directions?

my code:

#include <stdio.h>
#include <limits.h>

#define MAX_L 20 /* max lands */

long long int min(long long int a,long long int b) {
if( a > b ) return b;
else return a;
}

int main() {
/*freopen("in", "r", stdin);
freopen("out", "w", stdout); //*/

long long int lands[MAX_L][MAX_L];
int i, j, k, l;
int counter = 0;


/* initialize */
for(i=MAX_L-1; i>=0; i--)
for(j=MAX_L-1; j>=0; j--)
lands[j] = LONG_MAX;

while( scanf("%d", &k)!=EOF ) {
for(j=k-1; j>=0; j--) {
scanf("%d", &l);
lands[0][l-1] = lands[l-1][0] = 1;
}
for(i=MAX_L-3; i>=0; i--) {
scanf("%d", &k);
for(j=k-1; j>=0; j--) {
scanf("%d", &l);
lands[MAX_L-2-i][l-1] = lands[l-1][MAX_L-2-i] = 1;
}
}

/* Floyd-Warshall */
for(k=MAX_L-1; k>=0; k--)
for(i=MAX_L-1; i>=0; i--)
for(j=MAX_L-1; j>=0; j--)
lands[j] = min( lands[j], lands[k]+lands[k][j] );
/* Floyd-Warshall */

if(counter > 0)
printf("\n");
printf("Test Set #%d\n", ++counter);
scanf("%d", &k);
for(i=k-1; i>=0; i--) {
scanf("%d%d", &j, &l);
printf("%2d to %2d: %lld\n", j, l, lands[j-1][l-1]);
}

/* initialize */
for(i=MAX_L-1; i>=0; i--)
for(j=MAX_L-1; j>=0; j--)
lands[j] = LONG_MAX;
}

return 0;
}

[dodouuu]

AC.........

[Clark85]

Excuse me dodouuu...could tell me how did you make your code accepted? Thanks in advance.

[iqbal csedu]

I cant understand why i am getting worng answer.is there any one to help me
I used simple bfs.

Code: Select all

Code: Select all

#include<cstdio>
#include<queue>
using namespace std;

int g[21][21],d[21],seen[21];
int main()
{
	//freopen("output.txt","w",stdout);

	queue<int> q;

	int count=0,i,e,num,k,j,tc,s,u,v,source,destination;

	while(1)
	{
		for(i=0;i<=20;i++)
			for(j=0;j<20;j++)
				g[i][j]=0;
		for(i=1;i<=19;i++)
		{
			e=scanf("%d",&num);
			if(e!=1)
				return 0;

			for(j=1;j<=num;j++)
			{
				scanf("%d",&k);
				g[i][k]=1;
				g[k][i]=1;
			}
		}

	
		count++;

		scanf("%d",&tc);

		printf("Test Set #%d\n",count);

		for(i=1;i<=tc;i++)
		{
			for(j=0;j<=20;j++)
			{
				d[j]=0;
				seen[j]=0;
			}

			scanf("%d %d",&source,&destination);
			s=source;
			d[s]=0;
			seen[s]=1;
			q.push(s);

			while(q.empty()==0)
			{
				u=q.front();
				q.pop();
				for(v=1;v<=20;v++)
				{
					if(g[u][v]==1 && seen[v]==0)
					{
						d[v]=d[u]+1;
						seen[v]=1;
						q.push(v);
					}
				}
				if(seen[destination]==1)
				{
					printf("%2d to %2d: %d\n",source,destination,d[destination]);
					while(q.empty()==0)
						q.pop();
					break;
				}
			}
		}
		printf("\n");
	}
	return 0;
}

[sazzadcsedu]

check the following input (Sample input in the problem twice)

1 3
2 3 4
3 4 5 6
1 6
1 7
2 12 13
1 8
2 9 10
1 11
1 11
2 12 17
1 14
2 14 15
2 15 16
1 16
1 19
2 18 19
1 20
1 20
5
1 20
2 9
19 5
18 19
16 20
4 2 3 5 6
1 4
3 4 10 5
5 10 11 12 19 18
2 6 7
2 7 8
2 9 10
1 9
1 10
2 11 14
3 12 13 14
3 18 17 13
4 14 15 16 17
0
0
0
2 18 20
1 19
1 20
6
1 20
8 20
15 16
11 4
7 13
2 16
1 3
2 3 4
3 4 5 6
1 6
1 7
2 12 13
1 8
2 9 10
1 11
1 11
2 12 17
1 14
2 14 15
2 15 16
1 16
1 19
2 18 19
1 20
1 20
5
1 20
2 9
19 5
18 19
16 20
4 2 3 5 6
1 4
3 4 10 5
5 10 11 12 19 18
2 6 7
2 7 8
2 9 10
1 9
1 10
2 11 14
3 12 13 14
3 18 17 13
4 14 15 16 17
0
0
0
2 18 20
1 19
1 20
6
1 20
8 20
15 16
11 4
7 13
2 16

my ACC program gets

Test Set #1
1 to 20: 7
2 to 9: 5
19 to 5: 6
18 to 19: 2
16 to 20: 2

Test Set #2
1 to 20: 4
8 to 20: 5
15 to 16: 2
11 to 4: 1
7 to 13: 3
2 to 16: 4

Test Set #3
1 to 20: 7
2 to 9: 5
19 to 5: 6
18 to 19: 2
16 to 20: 2

Test Set #4
1 to 20: 4
8 to 20: 5
15 to 16: 2
11 to 4: 1
7 to 13: 3
2 to 16: 4


But your program output wrong.

[hotovaga]

hey can anyone pls help me, where is the problem in this code? I used bfs to solve this problem.Thanks in advance.

Code: Select all

#include<iostream>
#include<cstdio>
#include<queue>


using namespace std;

bool M[30][30];




int do_bfs(int city1,int city2)
{
	queue<int> q;
	int d[20]={0};
	bool seen[20];

	for(int i=0;i<20;i++)
		seen[i]=false;

	int s= city1 -1;  //source vertex;
	int destination= city2 -1; //destination vertex
	int v;

	seen[s]=true;
	d[s]=0;
	if(s==destination)
		return 0;
	q.push(s);

	while(!q.empty()){
		
		int u= q.front();
		q.pop();

	for(v=0;v<20;v++){

		if(M[u][v] && !seen[v]){
			seen[v]=true;
			d[v]=d[u]+1;
			if(v==destination)
				return d[v];
			else
			q.push(v);
		}

	}

	seen[u]=true;
	}
	return d[destination];
}



int main()
{
	int X,b,i,j,tc,city1,city2, ts=1;
	while(1){
		
		memset(M,0,sizeof(M));
		if(!(cin>>X)) break;
		
		for(i=0;i<X;i++){
			cin>>b;
			M[0][b-1]=1;
			M[b-1][0]=1;
		}

		for(i=1;i<19;i++){
			cin>>X;
			char c=getchar();
			if( X>0 && c=='\n'){
				tc=X;
				goto test_case;
			}
			for(j=0;j<X;j++){
				cin>>b;
				M[i][b-1]=1;
				M[b-1][i]=1;
			}
		}
		
		cin>>tc;
		test_case:
	
		cout<<"Test set #"<<ts++<<endl;
		for(i=0;i<tc;i++){
			cin>>city1>>city2;

			int res=do_bfs(city1,city2);

			
			printf("%2d to %2d:%2d\n",city1,city2,res);
		}
		cout<<endl;
	}

		return 0;
	}

[BUET]

what's the problem in this code?

Code: Select all

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<cstdio>

using namespace std;

#define  un 0
#define  dis 1
#define comp 2;


vector<int>adj[25];
queue<int> q;

int step;

int state[25];

bool flag[25];

int in_queue[25];

int p[25];

int src,dest;

int BFS()
{
      
      int u,i;
      
      

     memset(flag,false,sizeof(flag));

     memset(p,-1,sizeof(p));
     
     //state[src] = dis;

     p[src] = -1;

     flag[src] = true;
     
     q.push(src);
     
     while(!q.empty())
     {
          u = q.front();
          q.pop();

          int  tmp;
          int size;

          size = adj[u].size();

          for(i = 0; i < adj[u].size(); i++)
          {
               tmp = adj[u][i];

                   if(adj[u][i] == dest)
                   {
                              
                              step = 0;
                             p[adj[u][i]] = u;
                              int se = dest;
                              while(p[se] != -1)
                              {
                                     se = p[se];
                                     step++;
                               }
                               
                               while(!q.empty())
                                    q.pop();

                             //cout << "Finish\n";
                               
                               return 1;
                      
                      
                              
                 }
                 else
                 {
                     

                    if(flag[ adj[u][i] ] == false)
                    {
                        flag[ adj[u][i] ] = true;
                        p[adj[u][i]] = u;
                        q.push(adj[u][i]);
                    }
                }
             }
             
             state[u] = comp;
           
     }
     
     return 1;
      
}

int main(void)
{
     
     int i,j,a,b;
     
     
     
     int t = 1;;
     
     i = 0;
     
     while((scanf("%d",&a)) ==1)
     {

        //cin >> a;

        //if
            //return 0;

         for(j = 0; j<19; j++)
         {
                 if(j != 0)
                     cin >> a;
             for(i = 0;i < a; i++)
             {                     
                     cin >> b;
                   
                     adj[j+1].push_back(b);
                   adj[b].push_back(j+1);                                         
             } 
         }
         
         cin >> b;
         
         cout << "Test Set #" << t++ << endl;
         
         for( i = 0; i < b; i++)
         {
                cin >> src >> dest;
        
              BFS();
                
                printf("%2d to %2d: %d\n",src,dest,step);
              
         }

         cout << endl;

         for(i = 0; i <= 19;i++)
            if(!adj[i].empty())
                 adj[i].clear();

         
               
    }
     
     
     
     return 0;
}
[color=#FF80FF][color=#FF80FF][quote]"No quote"[/quote]

[Mohayemin]

Getting wrong answer:

The array GRAPH stores the graph.
GRAPH[0] stores the degree of i-th node.

Code: Select all

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>

#define SIZE 25

#define WHTE 0
#define GRAY 1
#define BLCK 2

using namespace std;

int GRAPH[SIZE][SIZE];

int BFS(int src, int dst);

int main (){	
	int N, u, v;
	int A, B;
	int d;
	int t = 0;
	int X, Y;
	while(scanf("%d", &X)!=EOF){
		for (u = 1; u <= 20; u++){
			GRAPH[u][0] = 0;			
		}
		
		u = 1;
		for (d = 1; d <= X; d++){
			scanf("%d", &Y);
			GRAPH[u][0]++;
			GRAPH[u][GRAPH[u][0]] = Y;
			GRAPH[Y][0]++;
			GRAPH[Y][GRAPH[Y][0]] = u;
		}
		
		for (u = 2; u <= 19; u++){
			scanf("%d", &X);
			GRAPH[u][0]+=X;
			
			for (d = 1; d <= X; d++){
				scanf("%d", &Y);
				GRAPH[u][0]++;
				GRAPH[u][GRAPH[u][0]] = Y;
				GRAPH[Y][0]++;
				GRAPH[Y][GRAPH[Y][0]] = u;
			}
		}
		
		scanf("%d", &N);
		printf("Test Set #%d\n", ++t);
		while (N--){
			scanf("%d %d", &A, &B);
			printf("%2d to %2d: %d\n", A, B, BFS(A, B));
		}
		
		puts("");
	}
	
	return 0;
}

int BFS(int src, int dst){
	int u, v;
	int V;
	int C[SIZE];
	int D[SIZE];
	int P[SIZE];
	
	queue<int> Q;
	
	if (src > dst){
		src^=dst;
		dst^=src;
		src^=dst;
	}
		
	for (u = 1; u <= 20; u++){
		C[u] = WHTE;
		D[u] = -1;
		P[u] = -1;
	}
	
	C[src] = GRAY;
	D[src] = 0;
	P[src] = -1;
	
	Q.push(src);

	while (!Q.empty()){
		u = Q.front();
		Q.pop();
		for (v = 1; v <= GRAPH[u][0]; v++){
			V = GRAPH[u][v];

			if (C[V] == WHTE){
				C[V] = GRAY;
				D[V] = D[u]+1;
				P[V] = u;
				Q.push(V);
			}
		}
		C[u] = BLCK;
	}
	
	return D[dst];
}

[live_lie]

you can use a simple bfs here....and check the output foramat....the newline metter.

[mahbub.cse.kuet]

Already got WA 7 times and I surprised why ? Need a kind person who provide me critical input ?
I used Floyd. Thanks in advance.

Code: Select all

int dist[22][22];

void Init()
{
    FOR(i, 0, 21) {
        FOR(j, 0, 21)
            dist[i][j] = INF;
        dist[i][i] = 0;
    }

}
void FloydWarshall()
{
    FOR(i, 0, 21)
        FOR(j, 0, 21)
            FOR(k, 0, 21)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main()
{
    READ("input.txt");
    WRITE("output.txt");

    int i, j, k;
    int TC, tc;
    int n, N, temp;
    int node, s, t;

    tc = 1;
    while(cin >> n) {
        Init();
        FOR(node, 1, 19) {
            if(node != 1) cin >> n;

            FOR(j, 1, n) {
                cin >> temp;
                dist[node][temp] = dist[temp][node] = 1;
            }
        }

        FloydWarshall();

        cout << "Test Set #" << tc++ << "\n";
        cin >> N;

        FOR(i, 1, N) {
            cin >> s >> t;
  //          printf("%2d to %2d: %d\n", s, t, dist[s][t]);
            printf("%2d to %2d: %d\n", s, t, dist[s][t]);
        }
        cout << "\n";
    }

	return 0;
}

[Blackwizard]

Hi...I've used bfs algorithm to solve this problem...it past sample input and some another testcases I've test...but I don't know why it goes wrong!!!
Here's my code...

Code: Select all

#include <iostream>
#include <queue>
#include <cstring>
#include <stdio.h>

using namespace std;

int mat[21][21];
int mark[21];
int tc = 0;
int n, m, t; 
int a, b;

void bfs ()
{
	queue <int> q;
	q.push (a);
	mark[a] = 0;
	while (!q.empty())
	{
		int temp = q.front();
		q.pop();
		if (temp == b)
			return;
		for (int i = 1; i <= 20; i++)
			if (mat[temp][i] == 1 && mark[i] == -1)
			{
				q.push (i);
				mark[i] = mark[temp] + 1;
			}
	}
}

int main ()
{
	//freopen ("input.in", "r", stdin);
	while (!cin.eof())
	{
		tc++;
		for (int i = 0; i < 21; i++)
			memset (mat[i], 0, sizeof mat[i]);
		for (int i = 1; i <= 19 && cin >> n; i++)
			for (int j = 0; j < n && cin >> m; j++)
			{
				mat[i][m] = 1;
				mat[m][i] = 1;
			}
		cin >> t;
		cout << "Test Set #" << tc << endl;
		for (int i = 0; i < t && cin >> a >> b; i++)
		{
			memset (mark, -1, sizeof mark);
			bfs ();
			printf ("%2d", a);
			cout << " to ";
			printf ("%2d", b);
			cout << ": " << mark[b] << endl;
		}
		cout << endl;
	}
	return 0;
}

[brianfry713]

Don't loop until !cin.eof(), that won't work if there is a space at the end of the input file.