Language: C++

#include <iostream>
#include <algorithm>
#include <vector>
#include <tr1/unordered_map>

using namespace std;
 
int n[2],m[2];
tr1::unordered_map< pair<string,string> , int > memo[501][501];
vector< vector<int> > a[2];
vector< vector<string> > b[2];
 
//OtAÅÌÔp1 , OtBÅÌÔp2 , OtAÅ¡Å«Ä¢é¶ñs1 , OtBÅ¡Å«Ä¢é¶ñs2
int dfs(int p1,int p2,string &s1,string &s2){
		// IÌÆ«ÌBs1Æs2ªêvµÄ¢é(Ì s1=s2=""Èç1Ô·»êÈOÈç0B
		if(p1 == n[0]-1 && p2 == n[1]-1) return (s1 == "" && s2 == "");
		
		// »
		if(memo[p1][p2].count(make_pair(s1,s2))) return memo[p1][p2][make_pair(s1,s2)];

		
		int ans = 0;
		
		// p1<=p2©ÂAAÅ®¯éÈçAAÅ®­B»êÈOÈçBÅ®­B
		if(p1 <= p2 || p2 == n[1]-1){
			for(int i = 0 ; i < a[0][p1].size() ; i++){
					//Æè ¦¸xÆyÉÎµAÌs1,s2óâÆµÄ¶ñÂ­éB
					string x = s1 + b[0][p1][i];
					string y = s2;
					int I = 0 , J = 0;
					//êvªð¦éB
					for( ; I < x.size() && J < y.size() && x[I] == y[J] ; ) I++ , J++ ;
					
					//ÇÁ¿©ªóÈç¡ÜÅêvµÄ¢éÆ¢¤±Æ¾©ç±sB
					if( I == x.size() || J == y.size() ){
							
							//Ü ±±ÍÁµÄ¢é¾¯
							if( I == x.size() && I == y.size() ) x = "" , y = "";
							else if( I == x.size() ) x = "" , y = y.substr(J);
							else if( J == y.size() ) x = x.substr(I) , y = "";
								
							//{¿Í±±
							ans = ( ans + dfs(a[0][p1][i],p2,x,y) ) % 1000000007;
					}
			}
		}else{
			//ãÆ¯¶
			for(int j = 0 ; j < a[1][p2].size() ; j++){
					string x = s1;
					string y = s2 + b[1][p2][j] ;
					int I = 0 , J = 0;
					for( ; I < x.size() && J < y.size() && x[I] == y[J] ; ) I++ , J++ ;
					if( I == x.size() || J == y.size() ){
							
							if( I == x.size() && I == y.size() ) x = "" , y = "";
							else if( I == x.size() ) x = "" , y = y.substr(J);
							else if( J == y.size() ) x = x.substr(I) , y = "";
							
							ans = ( ans + dfs(p1, a[1][p2][j],x,y) ) % 1000000007;
					}
			}
		}
		
		return memo[p1][p2][make_pair(s1,s2)] = ans;
}

int main(){
		int T;cin >> T;
		while(T--){
				for(int i = 0 ; i < 2 ; i++){
						cin >> n[i] >> m[i];
						//cout << n[i] << " " << m[i] << endl;
						a[i].clear(); b[i].clear(); a[i].resize((unsigned)n[i]) , b[i].resize((unsigned)n[i]);
						for(int j = 0 ; j < m[i] ; j++){
								int A,B; string C;
								cin >> A >> B >> C;
								a[i][A].push_back(B);
								b[i][A].push_back(C);
						}
				}
				for(int i = 0 ; i < 501 ; i++)
					for(int j = 0 ; j < 501 ; j++)
						memo[i][j].clear();
				string xnull , ynull;
				cout << dfs(0,0,xnull,ynull) << endl;
		}
}

Compiler output:
/usr/bin/ld: /tmp/cclR7VNm.o: in function `std::tr1::__detail::_Hash_code_base<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::pair<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > const, int>, std::_Select1st<std::pair<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > const, int> >, std::equal_to<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > >, std::tr1::hash<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > >, std::tr1::__detail::_Mod_range_hashing, std::tr1::__detail::_Default_ranged_hash, false>::_M_hash_code(std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > const&) const':
a.cc:(.text._ZNKSt3tr18__detail15_Hash_code_baseISt4pairINSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEES8_ES2_IKS9_iESt10_Select1stISB_ESt8equal_toIS9_ENS_4hashIS9_EENS0_18_Mod_range_hashingENS0_20_Default_ranged_hashELb0EE12_M_hash_codeERSA_[_ZNKSt3tr18__detail15_Hash_code_baseISt4pairINSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEES8_ES2_IKS9_iESt10_Select1stISB_ESt8equal_toIS9_ENS_4hashIS9_EENS0_18_Mod_range_hashingENS0_20_Default_ranged_hashELb0EE12_M_hash_codeERSA_]+0x37): undefined reference to `std::tr1::hash<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > >::operator()(std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >) const'
/usr/bin/ld: /tmp/cclR7VNm.o: in function `std::tr1::__detail::_Hash_code_base<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::pair<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > const, int>, std::_Select1st<std::pair<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > const, int> >, std::equal_to<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > >, std::tr1::hash<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > >, std::tr1::__detail::_Mod_range_hashing, std::tr1::__detail::_Default_ranged_hash, false>::_M_bucket_index(std::tr1::__detail::_Hash_node<std::pair<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > const, int>, false> const*, unsigned long) const':
a.cc:(.text._ZNKSt3tr18__detail15_Hash_code_baseISt4pairINSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEES8_ES2_IKS9_iESt10_Select1stISB_ESt8equal_toIS9_ENS_4hashIS9_EENS0_18_Mod_range_hashingENS0_20_Default_ranged_hashELb0EE15_M_bucket_indexEPKNS0_10_Hash_nodeISB_Lb0EEEm[_ZNKSt3tr18__detail15_Hash_code_baseISt4pairINSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEES8_ES2_IKS9_iESt10_Select1stISB_ESt8equal_toIS9_ENS_4hashIS9_EENS0_18_Mod_range_hashingENS0_20_Default_ranged_hashELb0EE15_M_bucket_indexEPKNS0_10_Hash_nodeISB_Lb0EEEm]+0x57): undefined reference to `std::tr1::hash<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > >::operator()(std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >) const'
collect2: error: ld returned 1 exit status