OJ Board

Code: Select all

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
vector<int>v[100];
int ans;
void bfs(int src,int des)
{
    queue<int>q;
    q.push(src);
    int taken[100]= {0},distance[100];
    taken[src]=1;
    distance[src]=0;
    while(!q.empty())
    {
        int u=q.front();
        for(int i=0; i<v[u].size(); i++)
        {
            int t=v[u][i];
            if(!taken[t])
            {
                distance[t]=distance[u]+1;
                taken[t]=1;
                q.push(t);
                if(t==des)
                {
                    ans=distance[t];
                    return;
                }
            }
 
        }
         q.pop();
    }
}
int main()
{
    int n,a,x,y,t,src,des,kase=1;
    while(cin>>n)
    {
        for(int i=1; i<=n; i++)
        {
            cin>>y;
            v[1].push_back(y);
            v[y].push_back(1);
        }
        for(x=2; x<20; x++)
        {
            cin>>n;
            for(int i=1; i<=n; i++)
            {
                cin>>y;
                v[x].push_back(y);
                v[y].push_back(x);
            }
 
        }
 
 
        //if(kase!=1)
        //puts("");
        printf("Test Set #%d\n",kase++);
        cin>>t;
        for(int i=1; i<=t; i++)
        {
            cin>>src>>des;
            printf("%2d to %2d: ",src,des);
            if(src==des)
            cout<<"0\n";
            else
            {
                bfs(src,des);
                cout<<ans<<endl;
            }
 
 
 
        }
       puts("");
        for(int i=0; i<20; i++)
            v[i].clear();
    }
 
}

Code: Select all

#include<stdio.h>
#include<string.h>

void BFS(int i);
int dequeue();
void enqueue(int k);

struct node {
	int node_value;
	char color[7];
} V[21];

int a[21][21];
int s[110][2];
int main()
{
	int i,j,n,m,N,T;
	T=1;
	for(i=1; i<=20; ++i)
	{
		for(j=1; j<=20; ++j)
			a[i][j] = 0;
	}
	while(scanf("%d",&n)==1)
	{
		for(j=1; j<=n; ++j)
		{
			scanf("%d",&m);
			a[1][m] = 1;
			a[m][1] = 1;
		}
		for(i=2; i<=19; ++i)
		{
			scanf("%d",&n);
			for(j=1; j<=n; ++j)
			{
				scanf("%d",&m);
				a[i][m] = 1;
				a[m][i] = 1;
			}	
		}
		scanf("%d",&N);
		for(i=1; i<=N; ++i)
		{
			scanf("%d %d",&s[i][0],&s[i][1]);
		}
		printf("Test Set #%d\n",T);
		T++;
		for(i=1; i<=N; ++i)
		{
			for(j=1; j<=20; ++j)
			{
				strcpy(V[j].color,"WHITE");
			}
			BFS(i);
			printf("%2d to %2d: %d\n",s[i][0],s[i][1],V[s[i][1]].node_value);
		}
		printf("\n");
		for(i=1; i<=20; ++i)
		{
			for(j=1; j<=20; ++j)
				a[i][j] = 0;
		}
	}
	return 0;
}
int Q[21];
int tail,front;
void BFS(int i)
{
	int u,k;
	strcpy(V[s[i][0]].color,"GRAY");
	V[s[i][0]].node_value = 0;
	tail = front = 0;
	Q[front] = s[i][0];
	tail++;
	while(front<=tail)
	{
		u = dequeue();
		for(k=1; k<=20; ++k)
		{
			if(a[u][k] == 1)
			{
				if(strcmp(V[k].color,"WHITE")==0)
				{
					strcpy(V[k].color,"GRAY");
					V[k].node_value = V[u].node_value+1;
					enqueue(k);
				}
			}
		}
	}
}

int dequeue()
{
	int x;
	if(front<=tail)
	{
		x = Q[front];
		front++;
		return x;
	}
	else
		return -1;
}
void enqueue(int k)
{
	if(tail<20)
	{
		Q[tail] = k;
		tail++;
	}
}

Code: Select all

//  Program : UVa 567 - Risk
//  Author  : Anindya Sundar Paul
//  Run-time:
//  Verdict : WA

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>

#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <bitset>

#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>

using namespace std;

#define EPS 1e-9
#define INF 2147483647
#define PI 3.14159265358979323846264338327950

#define MEM( x, y ) memset( x, y, sizeof( x ) )
#define READ( file ) freopen( file, "r", stdin )
#define WRITE( file ) freopen( file, "w", stdout )

#define PB( x ) push_back( x )
#define PF( x ) push_front( x )

typedef long long LL;
typedef unsigned long long ULL;

// Sieve Prime Generator
template <class T> T setBit( T n, T pos ) { return n = n | ( 1 << pos ); }
template <class T> bool checkBit( T n, T pos ) { return n & ( 1 << pos ); }

// Template ends, coding starts

int lev[21];
int visit[21];
int dis[21][21];

vector <int> node[21];

int findDis( int src, int lev );

int main()
{
    //READ( "i.txt" );

    int n, pos, from, to, line = 1, cs = 1;

    while( cin >> n ) {
        if( line < 20 ) {
            while( n-- ) {
                cin >> pos;
                node[line].PB( pos );
                node[pos].PB( line );
            }
            line++;
        }
        else {
            line = 1;
            if( cs != 1 ) puts( "" );
            cout << "Test Set #" << cs++ << endl;

            while( n-- ) {
                MEM( lev, 0 );
                MEM( visit, 0 );
                cin >> from >> to;
                printf( "%2d to %2d:%2d\n", from, to, findDis( from, to ) );
            }
            for( LL i = 0; i < 21; i++ )
                node[i].clear();
        }
    }

    return 0;
}

int findDis( int src, int target )
{
    LL f, x, i;
    queue <int> q;

    q.push( src );
    lev[src] = 0;
    visit[src] = 1;

    while( !q.empty() ) {
        f = q.front();
        if( f == target ) break;
        for( i = 0; i < node[f].size(); i++ ) {
            x = node[f][i];
            if( !visit[x] ) {
                lev[x] = lev[f] + 1;
                visit[x] = 1;
                q.push( x );
            }
        }
        q.pop();
    }

    return lev[f];
}

Code: Select all

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Bag<Integer>[] connect;
		boolean[] marked;
		int[] dist;
		int x;
		int q;
		int start;
		int end;
		int trial=1;
		Scanner in = new Scanner(System.in);
		while(in.hasNext())
		{
			connect =(Bag<Integer>[]) new Bag[21];  // if I had to guess, the problem is here, but i don't know why or how to fix it
			for(int i=0;i<21;i++)
			{
				connect[i]=new Bag<Integer>();
			}
			for(int i=1;i<20;i++)
			{	
				x=in.nextInt();
				for(int j=0;j<x;j++)
				{
					q=in.nextInt();

					connect[i].add(q);
					connect[q].add(i);
				}
			}
			x=in.nextInt();
			System.out.println("");
			System.out.println("Test Set #"+trial);
			trial++;
			
			for(int i=0;i<x;i++)
			{
				start=in.nextInt();
				end=in.nextInt();
				Queue<Integer> w = new Queue<Integer>();
				dist=new int[21];
				int[] edgeTo=new int[21];
				marked= new boolean[21];
				marked[start]=true;
				w.enqueue(start);
				while(!w.isEmpty())
				{
					q=w.dequeue();
					if(q==end)
						break;
					for(int z : connect[q])
					{
						if(!marked[z])
						{
							marked[z]=true;
						dist[z]=dist[q]+1;
						edgeTo[z]=q;
						w.enqueue(z);
						}
						}
				
				}
				System.out.printf("%2d to %2d: %-2d\n",start,end,dist[end]);
			}
			
		}
		System.out.println("");


	}


}