zoj 2560 I Just Called ...

#include <functional>#include <algorithm>#include <iostream>#include <iomanip>#include <numeric>#include <sstream>#include <cstring>#include <cstdio>#include <string>#include <vector>#include <bitset>#include <queue>#include <stack>#include <cmath>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define REP(i, n) for (int i=0;i<int(n);++i)#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)#define REP_1(i, n) for (int i=1;i<=int(n);++i)#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)#define REP_N(i, n) for (i=0;i<int(n);++i)#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)#define REP_1_N(i, n) for (i=1;i<=int(n);++i)#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)#define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i)#define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i)#define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i)#define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i)#define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i)#define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i)#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)#define DO(n) while(n--)#define DO_C(n) int n____ = n; while(n____--)#define _TO(i, a, b) int s_=a<b?1:-1,b_=b+s_;for(int i=a+s_;i!=b_;i+=s_)#define TO(i, a, b) int s_=a<b?1:-1,b_=b+s_;for(int i=a;i!=b_;i+=s_)#define TO_1(i, a, b) int s_=a<b?1:-1,b_=b;for(int i=a;i!=b_;i+=s_)#define SQZ(i, j, a, b) for (int i=int(a),j=int(b)-1;i<j;++i,--j)#define SQZ_1(i, j, a, b) for (int i=int(a),j=int(b);i<=j;++i,--j)#define REP_2(i, j, n, m) REP(i, n) REP(j, m)#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)#define ALL(A) A.begin(), A.end()#define LLA(A) A.rbegin(), A.rend()#define CPY(A, B) memcpy(A, B, sizeof(A))#define INS(A, P, B) A.insert(A.begin() + P, B)#define ERS(A, P) A.erase(A.begin() + P)#define BSC(A, X) find(ALL(A), X) // != A.end()#define CTN(T, x) (T.find(x) != T.end())#define SZ(A) int(A.size())#define PB push_back#define MP(A, B) make_pair(A, B)#define Rush int T____; RD(T____); DO(T____)#define Display(A, n, m) { REP(i, n){  REP(j, m) cout << A[i][j] << " ";cout << endl;}}#define Display_1(A, n, m) {REP_1(i, n){ REP_1(j, m) cout << A[i][j] << " ";cout << endl;}}#pragma comment(linker, "/STACK:36777216")typedef long long LL;typedef double DB;typedef long double LDB;typedef unsigned UINT;typedef unsigned long long ULL;typedef vector<int> VI;typedef vector<char> VC;typedef vector<string> VS;typedef vector<LL> VL;typedef vector<DB> VD;typedef set<int> SI;typedef set<string> SS;typedef set<LL> SL;typedef set<DB> SD;typedef map<int, int> MII;typedef map<string, int> MSI;typedef map<LL, int> MLI;typedef map<DB, int> MDI;typedef map<int, bool> MIB;typedef map<string, bool> MSB;typedef map<LL, bool> MLB;typedef map<DB, bool> MDB;typedef pair<int, int> PII;typedef pair<int, bool> PIB;typedef pair<DB, int> PDI;typedef vector<PII> VII;typedef vector<VI> VVI;typedef vector<VII> VVII;typedef set<PII> SII;typedef map<PII, int> MPIII;typedef map<PII, bool> MPIIB;template<class T> inline void RD(T &);template<class T> inline void OT(const T &);inline int RD(){ int x; RD(x); return x;}template<class T> inline T& _RD(T &x){ RD(x); return x;}inline void RC(char &c){scanf(" %c", &c);}inline char RC(){ char x; RC(x); return x;}inline void RS(char *s){scanf("%s", s);}template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}template<class T0, class T1, class T2> inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);}template<class T0, class T1, class T2, class T3> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3);}template<class T0, class T1, class T2, class T3, class T4> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);}template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);}template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);}template<class T0, class T1> inline void OT(T0 &x0, T1 &x1){OT(x0), OT(x1);}template<class T0, class T1, class T2> inline void OT(T0 &x0, T1 &x1, T2 &x2){OT(x0), OT(x1), OT(x2);}template<class T0, class T1, class T2, class T3> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);}template<class T0, class T1, class T2, class T3, class T4> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}template<class T0, class T1, class T2, class T3, class T4, class T5> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);}template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}template<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}template<class T> inline void CLR(priority_queue<T, vector<T>, less<T> > &Q){ while (!Q.empty()) Q.pop();}template<class T> inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q){ while (!Q.empty()) Q.pop();}template<class T> inline void CLR(T &A){A.clear();}template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);}template<class T0, class T1, class T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2){CLR(A0), CLR(A1), CLR(A2);}template<class T0, class T1, class T2, class T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);}template<class T0, class T1, class T2, class T3, class T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}template<class T0, class T1, class T2, class T3, class T4, class T5> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);}template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);}template<class T> inline void CLR(T &A, int n){REP(i, n) CLR(A[i]);}template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}template<class T0, class T1> inline void FLC(T0 &A0, T1 &A1, int x){FLC(A0, x), FLC(A1, x);}template<class T0, class T1, class T2> inline void FLC(T0 &A0, T1 &A1, T2 &A2){FLC(A0), FLC(A1), FLC(A2);}template<class T0, class T1, class T2, class T3> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3){FLC(A0), FLC(A1), FLC(A2), FLC(A3);}template<class T0, class T1, class T2, class T3, class T4> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4);}template<class T0, class T1, class T2, class T3, class T4, class T5> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5);}template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5), FLC(A6);}template<class T> inline void SRT(T &A){sort(ALL(A));}template<class T, class C> inline void SRT(T &A, C B){sort(ALL(A), B);}const int MOD = 1000000007;const int INF = 0x3f3f3f3f;const DB EPS = 1e-8;const DB OO = 1e15;const DB PI = M_PI; template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;}template<class T> inline void checkMax(T &a,const T b){if (b>a) a=b;}template <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;}template <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;}template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}template<class T> inline T max(T a, T b, T c, T d){return max(min(a, b), max(c, d));}template<class T, class C> inline T min_cp(T a, T b, C cp){return min(a, b, cp);}template<class T, class C> inline T min_cp(T a, T b, T c, C cp){return min_cp(min_cp(a, b, cp), c, cp);}template<class T, class C> inline T min_cp(T a, T b, T c, T d, C cp){return min_cp(min_cp(a, b, cp), min_cp(c, d, cp), cp);}template<class T, class C> inline T max_cp(T a, T b, C cp){return max(a, b, cp);}template<class T, class C> inline T max_cp(T a, T b, T c, C cp){return max_cp(max_cp(a, b, cp), c, cp);}template<class T, class C> inline T max_cp(T a, T b, T c, T d, C cp){return max_cp(max_cp(a, b, cp), max_cp(c, d, cp), cp);}template<class T> inline T sqr(T a){return a*a;}template<class T> inline T cub(T a){return a*a*a;}int Ceil(int x, int y){return (x - 1) / y + 1;}inline int rand32(){return (bool(rand() & 1) << 30) | (rand() << 15) + rand();}inline int random32(int l, int r){return rand32() % (r - l + 1) + l;}inline int random(int l, int r){return rand() % (r - l + 1) + l;}int dice(){return rand() % 6;}bool coin(){return rand() % 2;}template<class T> inline void RD(T &x){ char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';}template<class T> inline void OT(const T &x){ cout << x << endl;}const int N = 10009, M = 209, L = 1009, S = 500009;int trie[S][10], bj[S], tot; char str[L];int w[4][4], ri[N], pos[N], si[M], cov[M];int n, m, home, from, target, _;int New_node(){ bj[tot] = 0, RST(trie[tot]); return tot++;}#define c str[i] - '0'#define v trie[u][c]int Insert(int u = 0) { RS(str); REP_C(i, strlen(str)){ if (!v) v = New_node(); u = v;}return u;}int Search(int u = 0){ RS(str); REP_C(i, strlen(str)){ if (!v) break; u = v; }return bj[u];}int init() {RST(trie[0]), tot = 1; RST(cov);REP_1(i, m) RD(si[i]), pos[i]=Insert(); int pi; REP_1(i, n){RD(ri[i], pi); if(!pi) bj[pos[ri[i]]] = i;else DO(pi) bj[Insert(pos[ri[i]])] = i;}RD(home); Rush cov[RD()] = true;REP_2(i, j, 4, 4) RD(w[i][j]);}inline int st(){if(ri[from]==home) return 0;if (cov[ri[from]]) return si[ri[from]] == si[home] ? 1 : 2;return 3;}inline int ed(){if(target==from) return 0;if(ri[target]==ri[from]) return 1;if(cov[ri[target]]) return 2;return 3;}int main() { while (scanf("%d%d%d%d", &n, &m, &_, &_) != EOF){ init(); LL res = 0, T; Rush{ RD(from), target = Search(); RD(T); if(!target) continue; res += T * w[st()][ed()]; } OT(res); }}