OJ Board

Code: Select all

#pragma warning ( disable : 4786 )
#include<stdio.h>
#include<vector>
#include<queue>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
#define max 5000

vector<string> K(100000);
bool adj[max][max],T[max];
int node,D[max],H[max];

void Ini(string s){
	int i;
	for(i=0;i<node;i++)
		if(K[i]==s) return;
		K[node++]=s;
		return;
}

int hash(string s){
	int i;
	for(i=0;i<node;i++)
		if(K[i]==s)return i;
		return i;
}

void bfs(string s,string d){
	int i,j,k,b=0;
	i=hash(s);
	j=hash(d);
	queue<int> Q;
	Q.push(i);
	D[i]=0;
	T[i]=false;
	while(!Q.empty()){
		k=Q.front();
		Q.pop();
		for(i=0;i<node;i++)
			if(adj[k][i]&&T[i]){
				D[i]=k;
				T[i]=false;
				Q.push(i);
				if(i==j){b=1;break;}
			}
			if(b==1)break;
	}
	i=0;
	k=0;
	if(b==1){
		while(1){
			H[k++]=j;
			j=D[j];
			if(j==i)break;
		}
		for(i=k-1;i>=0;i--){
			cout<<K[D[H[i]]]<<" "<<K[H[i]];
			printf("\n");
		}
	}
	if(b==0) printf("No route\n");




}

int main(){
	char x[10],y[10];
	int i,j,g,z;
	string s,v;
	bool u=false;
		while(scanf("%d",&g)!=EOF){
			node=0;
			if(u)printf("\n");
	        memset(adj,false,sizeof(adj));
	        memset(D,0,sizeof(D));
	        memset(T,true,sizeof(T));
			for(z=0;z<g;z++){
				scanf("%s %s",x,y);
				s=x;
				v=y;
		        Ini(s);
		        Ini(v);
		        i=hash(s);
		        j=hash(v);
		        adj[i][j]=true;
		        adj[j][i]=true;
			}
			
	scanf("%s %s",x,y);
	s=x;
	v=y;		
	bfs(s,v);
	u=true;
		}
	

	return 0;
}

Code: Select all

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<string>
#include<cstring>

using namespace std;

vector<long>G[5000];

map<string,long>indx;

string a[5000];

long path[10000];

long graph_input(long edge)
{
    long i,j,node;

    string b[5000];

    char x[5],y[5];

    node=0;

    j=0;

    for(i=0; i<edge; i++)
    {
        cin>>a[j]>>a[j+1];
        j+=2;
    }

    for(i=0; i<j; i++)
    {
        b[i]=a[i];
    }

    sort(a,a+j);

    node = unique(a,a+j)-a;

    for(i=0; i<node; i++)
    {
        indx[a[i]]=i;
    }

    for(i=0; i<j; i+=2)
    {
        G[indx[b[i]]].push_back(indx[b[i+1]]);
        G[indx[b[i+1]]].push_back(indx[b[i]]);
    }

    return node;
}

int bfs(long n,long src,long dest)
{
    long k=0,i,taken[5000]= {0};

    queue<long>Q;

    Q.push(src);

    taken [src]=1;

    while(!Q.empty())
    {
        long u=Q.front();

        for(i=0; i<G[u].size(); i++)
        {
            long v=G[u][i];

            if(!taken[v])
            {
                taken[v]=1;

                path[v]=u;

                if(v==dest)
                    return 1;

                Q.push(v);
            }
        }
        Q.pop();
    }

return 0;
}

int main()
{
    //freopen("out.txt","w",stdout);

    long i,j,k,x,y,node,edge,flag=0;

    char src[5],dest[5];

    while(scanf("%ld",&edge)!=EOF)
    {
        if(flag)
            printf("\n");

        flag=1;

        node = graph_input(edge);

        scanf("%s %s",src,dest);

        if(strcmp(src,dest)==0)
            printf("%s %s\n",src,dest);

        else
        {

            k=bfs(node,indx[src],indx[dest]);

            if(k)
            {
                long destination=indx[dest],k=0,sol[10000]= {0};

                while(destination!=indx[src])
                {
                    sol[k++]=destination;

                    destination=path[destination];
                }
                sol[k++]=destination;

                while(--k>0)
                {
                    cout<<a[sol[k]]<<" "<<a[sol[k-1]]<<endl;
                }
            }
            else
                printf("No route\n");
        }

        for(i=0; i<node; i++)
        {
            G[i].clear();
        }

        indx.clear();

    }
    return 0;
}

Code: Select all

0
AA BB

1
AA BB
CC BB

1
AA BB
GG PP

2
AA BB
BB CC
GG GG

4
AB JK
PO LK
QW PO
LK AB
AB PO

Code: Select all

No route

No route

No route



AB LK
LK PO

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <string>
#include <cctype>
#include <algorithm>
#include <bitset>
#include <set>
using namespace std;

vector<int>node[100];
map<string , int > mp;
vector<int>rasta;
int parent[50000];
int bfs(int source,int termint)
{
    for(int i=0;i<5000;i++)
        parent[i] = i;
    queue<int>qu;
    qu.push(source);
    int taken[10000]={0};
    taken[source]=1;
    int reach=0;
    while(!qu.empty())
    {
        int u=qu.front();
        for(int i=0;i<node[u].size();i++)
        {
            int v=node[u][i];
            if(!taken[v])
            {
                parent[v]=u;
                taken[v]=1;
                if(v ==termint)
                {
                    while(!qu.empty())
                        qu.pop();
                    return 1;
                }
                qu.push(v);

            }
        }
        qu.pop();
    }
    return -1;
}


int find_route(int m)
{
    if(parent[m]==m)
    {
        rasta.push_back(m);
        return 0;
    }
    else
    {
        rasta.push_back(m);
        find_route(parent[m]);
    }
}
int main()
{

    int a;
    string s1,s2;
    vector<string>road_name;
    int aa=0;
    
    while(scanf("%d",&a)!=EOF)
    {
        if(aa!=0)
            cout<<endl;
        aa++;
        int j=1;
        for(int i=0;i<a;i++)
        {
            cin>>s1>>s2;
            if(mp.find(s1)==mp.end())
            {
                mp[s1]=j++;
                road_name.push_back(s1);
            }
            if(mp.find(s2)==mp.end())
            {
                mp[s2]=j++;
                road_name.push_back(s2);
            }
            node[mp.find(s1)->second].push_back(mp.find(s2)->second);
            node[mp.find(s2)->second].push_back(mp.find(s1)->second);
        }
        cin>>s1>>s2;
        int val = bfs(mp.find(s1)->second,mp.find(s2)->second);

        if(val == -1)
            cout<<"No route"<<endl;
        else
        {
            find_route(mp.find(s2)->second);
            reverse(rasta.begin(),rasta.end());
            for(int i=0;i<rasta.size()-1;i++)
                cout<<road_name[rasta[i]-1]<<" "<<road_name[rasta[i+1]-1]<<endl;
        }
        rasta.clear();
        road_name.clear();
        mp.clear();
        for(int i=0;i<100;i++)
            node[i].clear();
    }
    return 0;
}

Code: Select all

removed after AC.

Code: Select all

Removed After AC