UVa 762 - We Ship Cheap

Problem

Solve for the fastest parcel shipping path built by the city. The cost between each two citys are the same. The city defined in two capital letters.

Algorithm

BFS. Using bfs to solve the shortest path problem.

Code

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

using namespace std;

map <string, vector<string> > adjacency_list; 
int bfs(string s, string t)
{
	map <string, int> visit; 
	visit[s] = 1;
	map <string, string> parent; 
	parent[s] = s;
	queue<string> Q;
	Q.push(s);
	string Now, New;
	while (!Q.empty()) {
		Now = Q.front(); Q.pop();
		for (int i = adjacency_list[Now].size()-1; i >= 0; -- i) {
			New = adjacency_list[Now][i];
			if (!visit[New]) {
				visit[New] = 1;
				parent[New] = Now;
				Q.push(New);
				if (New == t) {
					stack <string> S;
					while (New != s) {
						S.push(New);
						New = parent[New];
					}
					New = s;
					while (!S.empty()) {
						cout << New << " ";
						New = S.top();
						cout << New << endl;
						S.pop(); 
					}
					return 1;
				}
			}
		}
	}
 	std::cout << "No route" << std::endl;
 	return 0;
 }

int main()
{
	int n, cases = 0;
	string s, t;
	while (cin >> n) {
		adjacency_list.clear();
		for (int i = 0; i < n; ++ i) {
			cin >> s >> t;
			adjacency_list[s].push_back(t);
			adjacency_list[t].push_back(s);
		}
		cin >> s >> t;
		
		if (cases ++)
			cout << endl;
		bfs(s, t);
		
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70