OJ Board

Code: Select all

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

using namespace std;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;


map<int, vi> graph;
map<string, string> parent;
map <string, int> indexes;
map <int, string> cities;

void backtrack(string begin, string end) {
	stack<string> path;
	string x = end;
	while (true) {
		if (parent.count(x)) {
			path.push(x);
			x = parent[x];
		}
		else break;
	}
	string last;
	for (int i = 0; i < (int)path.size(); i++) {
		cout << parent[path.top()] << " " << path.top() << endl;
		last = path.top();
		path.pop();
	}
	if (last != end)
		cout << last << " " << end << endl;
 
 }


int main () {
	int t, cont = 0;
	
	while (scanf("%d", &t) != EOF) {
		if (cont)
			printf("\n");
		int idx = 0;
		graph.clear();
		indexes.clear();
		parent.clear();
		cities.clear();
		for (int i = 0; i < t; i++) {
			string a, b;
			cin >> a >> b;
			if (!indexes.count(a)) {
				indexes[a] = idx;
				cities[idx] = a;
				idx++;
			}
			if (!indexes.count(b)) {
				indexes[b] = idx;
				cities[idx] = b;
				idx++;
			}
			graph[indexes[a]].push_back(indexes[b]);
			graph[indexes[b]].push_back(indexes[a]);
		}

		string init, dest;
		cin >> init >> dest;
		if (init == dest) {
			cout << init << " " << dest << endl;
			cont++;
			continue;
		}
		if (!indexes.count(init)) {
			printf("No route\n");
			cont++;
			continue;
		}
		int begin = indexes[init];
		int end = indexes[dest];
		queue<int> q;
		q.push(begin);
		map<int, int> dist;
		dist[begin] = 0;
		bool found = false;

		while (!q.empty() && !found) {
			int u = q.front();
			q.pop();
			for (int i = 0; i < (int)graph[u].size(); i++) {
				int v = graph[u][i];
				if (!dist.count(v)) {
					dist[v] = dist[u] + 1;
					q.push(v);
					parent[cities[v]] = cities[u];
					if (v == end) {
						found = true;
						break;
					}
				}
			}
		}
		if (found) {
			backtrack(init, dest);
		}
		else
			printf("No route\n");
		cont ++;
	}

	return 0;
}

Code: Select all

1
AA BB
BB CC

Code: Select all

#include<bits/stdc++.h>
using namespace std;
map<string,int>m;
vector<int>v[100];
int visited[100];
int parent[100];
vector<int>sv;
vector<string>ss;
void bfs(int src,int d)
{
    queue<int>q;

   memset(visited,-1,sizeof(visited));
   memset(parent,-1,sizeof(parent));

   visited[src]=0;
   q.push(src);
   int u,r;
   while(!q.empty())
   {
     int a=q.front();
      q.pop();
    for(int i=0;i<v[a].size();i++)
  {

    u=v[a][i];
     if(visited[u]==-1)
    {
        visited[u]=visited[a]+1;
        parent[u]=a;
        q.push(u);
    }
    if(u==d)break;
  }

}
if(visited[d]==-1){cout<<"No route"<<endl;return;}
  r=d;
  sv.push_back(r);
  r=parent[r];
  while(r!=src)
  {
      sv.push_back(r);
  r=parent[r];
  }
  sv.push_back(r);
  reverse(sv.begin(),sv.end());
  for(int i=0;i<sv.size()-1;i++)
    cout<<ss[sv[i]]<<" "<<ss[sv[i+1]]<<endl;

}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    string s,s1;
 char x,y,z;
 int l=0,i,edge;

bool p=0;
while(scanf("%d",&edge)!=EOF)
    {
    	//if(edge==0){cin>>s>>s1;continue;}
        l=0;
   if(p)cout<<endl;
     for(int k=0;k<edge;k++)
     {
         cin>>s>>s1;
         if(m.find(s)==m.end()){m[s]=l;ss.push_back(s);l++;}
         if(m.find(s1)==m.end()){m[s1]=l;ss.push_back(s1);l++;}

         v[m[s]].push_back(m[s1]);
         v[m[s1]].push_back(m[s]);
     }
     cin>>s>>s1;
     if(s==s1)cout<<s<<" "<<s1<<endl;
    else if(m.find(s)==m.end()||m.find(s1)==m.end())cout<<"No route"<<endl;
    else bfs(m[s],m[s1]);

     ss.clear();
     m.clear();
     for(int k=0;k<100;k++)v[k].clear();
     sv.clear();
     p=true;
     getchar();
    }
    //else return 0;


   return 0;
 }