blob: f14b731792ae1086dd5ff8563ee93650e60db191 (
plain)
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
|
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
using namespace std;
int main(){
int tc;
cin>>tc;
while(tc--){
int r, q, c1, c2;
char city1[100], city2[100];
int map[26][26] = {0};
cin>>r>>q;
while(r--){
cin>>city1>>city2;
c1 = (int)city1[0] % 65;
c2 = (int)city2[0] % 65;
map[c1][c2] = 1;
map[c2][c1] = 1;
}
while(q--){
string path="";
cin>>city1>>city2;
c1 = (int)city1[0] % 65;
c2 = (int)city2[0] % 65;
//BFS
bool visited[26]={false};
stack<int> s;
stack<string> p;
int start = c1;
string c;
s.push(start);
c = char(s.top()+65);
p.push(c);
p.push(c);
while(s.top()!=c2){
start = s.top();
s.pop();
visited[start]=true;
for(int i=0; i<26; i++)
if(start!=i && map[start][i]==1 && !visited[i])
s.push(i);
}
// for(int i=0; i<s.size(); i++){
// c= char(s.top()+65);
// path+=c;
// s.pop();
// }
cout<<path<<endl;
}
}
}
|
