diff options
Diffstat (limited to '10009')
| -rw-r--r-- | 10009/roads.cpp | 62 | ||||
| -rw-r--r-- | 10009/roads.in | 12 |
2 files changed, 74 insertions, 0 deletions
diff --git a/10009/roads.cpp b/10009/roads.cpp new file mode 100644 index 0000000..f14b731 --- /dev/null +++ b/10009/roads.cpp @@ -0,0 +1,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; + } + } +} + diff --git a/10009/roads.in b/10009/roads.in new file mode 100644 index 0000000..b15368d --- /dev/null +++ b/10009/roads.in @@ -0,0 +1,12 @@ +1 +7 3 +Rome Turin +Turin Venice +Turin Genoa +Rome Pisa +Pisa Florence +Venice Athens +Turin Milan +Turin Pisa +Milan Florence +Athens Genoa
\ No newline at end of file |