627

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

using namespace std;

vector<int> vb[305];
vector<int> par;

bool bfs(int path[],int st,int ed)
{
	int visit[400];
	for(int i=0;i<400;i++)
	visit[i]=0;
	queue<int> q;
	q.push(st);
	visit[st]=1;
	int a,b;
	if(st==ed)
		return 1;
	while(!q.empty())
	{
		a = q.front();q.pop();
		if(a==ed)
		return 1;
		for(int i=0;i<vb[a].size();i++)
		{
			b =  vb[a][i];
			if(visit[b]==0)
			{
				visit[b]=1;
				q.push(b);
				path[b]=a;
			}
		}
	}
	return 0;
}

int main()
{
	int router,qry;
	int fr,to,st,ed,i;
	string str;
	while(scanf("%d",&router)!=EOF)
	{
		getchar();
		for(int II=0;II<305;II++)
		vb[II].clear();
		for(int II=0;II<router;II++)
		{
			getline(cin,str);
			i=0;
			fr=0;
			while(str[i]!='-')
			{
				fr *= 10;fr += (str[i++]-'0');
			}
			i+=1;
			to=0;
			while(i<str.size())
			{
				if(str[i]==',')
				{
					vb[fr].push_back(to);
					to=0;
					i+=1;
				}
				else
				{
					to *= 10;
					to += (str[i++]-'0');
				}
			}
			vb[fr].push_back(to);
		}
		scanf("%d",&qry);
		for(int II=0;II<qry;II++)
		{
			scanf("%d%d",&st,&ed);
			int *path = new int[router+5];
			for(int JJ=0;JJ<router+5;JJ++)
			path[JJ]=JJ;
			bool f = bfs(path,st,ed);
			if(II==0)
				printf("-----\n");
			if(!f)
			printf("connection impossible\n");
			else
			{
				//cout<<"path = "<<path[5]<<"\n";
				int cc = ed;
				par.clear();
				while(path[cc]!=cc)
				{
					par.push_back(cc);
					cc=path[cc];
				}
				par.push_back(cc);
				for(int LL=par.size()-1;LL>=0;LL--)
				printf("%d%s",par[LL],LL==0?"\n":" ");
			}
			delete path;
		}
	}
	return 0;
}

There is another solution using Linked List in case Router ID is not limited from 1 to 300. But for this problem this solution gets TLE.

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

using namespace std;

struct Node{
	int number;
	Node *next;
};
struct Edge{
	int from,to;
	Edge *next;
	Edge(int f,int t);
};

Node *nodeList=0;
Edge *edgeList=0;
int IndexOfId[400];
vector<int> vb[400];
vector<int> par;

int GetNodeIndex(int num)
{
	Node *p=nodeList;
	int idx=0;
	while(p->next)
	{
		p=p->next;
		if(p->number==num)
		return idx;
		idx+=1;
	}
	p->next=new Node();
	p=p->next;
	p->number=num;
	p->next=0;
	IndexOfId[idx]=num;
	return idx;
}

Edge::Edge(int f,int t)
{
	from = f;
	to = t;
}

void init()
{
	Node *p=nodeList,*q;
	memset(IndexOfId,0,sizeof(IndexOfId));
	while(p)
	{
		q = p;
		p = p->next;
		delete q;
	}
	nodeList = new Node();
	nodeList->next=0;
	nodeList->number=-100;

	Edge *pp=edgeList,*tmp;
	while(pp)
	{
		tmp=pp;
		pp=pp->next;
		delete tmp;
	}
}

int CountNode()
{
	Node *p=nodeList->next;
	int cnt=0;
	while(p)
	{
		cnt+=1;
		p=p->next;
	}
	return cnt;
}

bool bfs(int path[],int st,int ed)
{
	int visit[400];
	for(int i=0;i<400;i++)
	visit[i]=0;
	queue<int> q;
	q.push(st);
	visit[st]=1;
	int a,b;
	if(st==ed)
		return 1;
	while(!q.empty())
	{
		a = q.front();q.pop();
		if(a==ed)
		return 1;
		for(int i=0;i<vb[a].size();i++)
		{
			b =  vb[a][i];
			if(visit[b]==0)
			{
				visit[b]=1;
				q.push(b);
				path[b]=a;
			}
		}
	}
	return 0;
}
int main()
{
	int n,m,fr,to,i;
	int a,b;
	string str;
	while(scanf("%d",&n)!=EOF)
	{
		getchar();
		init();
		for(int II=0;II<n;II++)
		{
			getline(cin,str);
			i=0;
			fr=0;
			while(str[i]!='-')
			{
				fr *= 10;fr += (str[i++]-'0');
			}
			fr = GetNodeIndex(fr);
			to=0;
			i+=1;
			while(i<str.size())
			{
				if(str[i]==',')
				{
					to = GetNodeIndex(to);
					Edge *e=new Edge(fr,to);
					e->next = edgeList;
					edgeList = e;
					to=0;
					i+=1;
				}
				else
				{
					to *= 10; to += (str[i++]-'0');
				}
			}
			to = GetNodeIndex(to);
			Edge *e=new Edge(fr,to);
			e->next = edgeList;
			edgeList = e;

		}
		int nodeCount = CountNode();
		for(int II=0;II<400;II++)
			vb[II].clear();
		Edge *tmpEdge=edgeList;
		while(tmpEdge)
		{
			a = tmpEdge->from;
			b = tmpEdge->to;
			vb[a].push_back(b);
			tmpEdge=tmpEdge->next;
		}
		scanf("%d",&m);
		for(int II=0;II<m;II++)
		{
			int st,ed;
			scanf("%d%d",&st,&ed);
			st=GetNodeIndex(st);
			ed=GetNodeIndex(ed);
			int *path = new int[nodeCount];
			for(int KK=0;KK<nodeCount;KK++)
			path[KK]=KK;
			bool f = bfs(path,st,ed);
			if(II==0)
				printf("-----\n");
			if(!f)
			printf("connection impossible\n");
			else
			{
				int cc = ed;
				par.clear();
				while(path[cc]!=cc)
				{
					par.push_back(cc);
					cc=path[cc];
				}
				par.push_back(cc);
				for(int LL=par.size()-1;LL>=0;LL--)
				printf("%d%s",IndexOfId[par[LL]],LL==0?"\n":" ");
			}
			delete path;
		}
	}
	return 0;
}