记录编号	193383	评测结果	AAAAAAAAAA
题目名称	神奇宝贝大师	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.079 s
提交时间	2015-10-14 18:14:10	内存使用	38.62 MiB

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
const int inf=1061109567;
const int maxn=200;
const int maxm=10000010;
const int mod=10000007;

map<string,int> num;
int v[maxn],val[maxn];
int p[maxn];
int d[maxn][maxn];
int f[maxm];
int vis[maxn],dir[maxn];

int Swap(int &a,int &b) {int t=a;a=b;b=t;}

int found(int x) {return (p[x]==x)?x:p[x]=found(p[x]);}

int main()
{
    freopen("pokemonmaster.in","r",stdin);
    freopen("pokemonmaster.out","w",stdout);
    //clock_t st=clock();
    memset(d,0x3f,sizeof(d));
    string name1,name2;
    int n1,n2;
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>name1;
        num[name1]=i;
        scanf("%d",&v[i]);
        p[i]=i;
    }
    int m;scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        cin>>name1>>name2;
        n1=found(num[name1]);
        n2=found(num[name2]);
        if(n1!=n2)
        {
            p[n1]=n2;
        }
    }
    int cnt=1;
    for(int i=1;i<=n;i++)
    {
        int t=found(i);
        if(!vis[t])
        {
            vis[t]=1;
            dir[t]=cnt++;
        }
    }
    for(int i=1;i<=n;i++) val[dir[found(i)]]+=v[i];
    cnt--;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        cin>>name1>>name2;
        n1=dir[found(num[name1])];
        n2=dir[found(num[name2])];
        scanf("%d",&d[n1][n2]);
        d[n2][n1]=d[n1][n2];
    }
    for(int k=1;k<=cnt;k++)
    {
        for(int i=1;i<=cnt;i++)
        {
            for(int j=1;j<=cnt;j++)
            {
                if(d[i][j]>d[i][k]+d[k][j])
                    d[i][j]=d[i][k]+d[k][j];
            }
        }
    }
    int money;cin>>name1;n1=dir[found(num[name1])];
    scanf("%d",&money);
    for(int i=1;i<=cnt;i++)
    {
        if(i==n1||d[i][n1]==inf) continue;
        for(int j=money;j>=d[i][n1];j--)
            f[j]=max(f[j],f[j-d[i][n1]]+val[i]);
    }
    printf("%d\n",f[money]%mod);
    int q;scanf("%d",&q);
    while(q--)
    {
        cin>>name1>>name2;
        n1=dir[found(num[name1])];
        n2=dir[found(num[name2])];
        if(d[n1][n2]!=inf) printf("%d\n",d[n1][n2]);
        else printf("-1\n");
    }
    //clock_t ed=clock();
    //printf("\nTime used : %.5lf Ms\n",double(ed-st)/CLOCKS_PER_SEC);
    return 0;
}