记录编号	154669	评测结果	AAAAAAAAAA
题目名称	神奇宝贝大师	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.060 s
提交时间	2015-03-23 20:10:52	内存使用	76.77 MiB

#include <fstream>
#include <map>
#include <algorithm>
using namespace std;
ifstream in("pokemonmaster.in");
ofstream out("pokemonmaster.out");
const int O=201; 
int w[O]={0},we[O]={0},v[O]={0},value[O]={0},way[O][O]={0},F[O]={0},p[O]={0},g[O]={0};//并查集
int f[20000001]={0},ans=0,n=0,m=0,q=0,k=0,start=0,sum=0;
map<string,int> change;
int link(int x,int y)
{
	if(g[x]>g[y])p[y]=x;
	else
	{
		p[x]=y;
		if(g[x]==g[y])g[y]+=1;
	}
	return 0;
}
int find(int x)
{
	if(p[x]!=x)p[x]=find(p[x]);
	return p[x];
}
int main()
{
	int i=0,j=0,lishi=0,qu=0,rub=0;string x1,x2;bool have[O]={0};
	in>>n;
	for(i=1;i<=n;i++)
	{
		lishi++;
		in>>x1;
		change[x1]=lishi;
		p[lishi]=lishi;
		in>>value[i];
	}
	in>>m;
	for(i=1;i<=m;i++)
	{
		in>>x1>>x2;
		link(find(change[x1]),find(change[x2]));
	}
	for(i=1;i<=n;i++)
	{
		string we;
		rub=find(i);
		if(have[rub]==0)
		{
			have[rub]=1;
			qu++;
			F[rub]=qu;
		}
	}
	for(i=1;i<=n;i++)
	{
		w[F[find(i)]]+=value[i];
	}
	for(i=1;i<=qu;i++)
	{
		for(j=1;j<=qu;j++)
		{
			way[i][j]=99999999;
		}
	}
    in>>k;
	for(i=1;i<=k;i++)
	{
		string x1,x2;int KFC=0;
		int li1=0,li2=0;
		in>>x1>>x2>>KFC;
		li1=F[find(change[x1])];
		li2=F[find(change[x2])];
		//out<<li1<<' '<<li2<<' '<<KFC<<endl;
		way[li1][li2]=KFC;
		way[li2][li1]=KFC;
	}
	for(k=1;k<=qu;k++)
		for(i=1;i<=qu;i++)
			for(j=1;j<=qu;j++)
			{
				if(way[i][k]+way[k][j]<way[i][j])way[i][j]=way[i][k]+way[k][j];
			}
	
    string asmdef;
	in>>asmdef;
	start=F[find(change[asmdef])];
	in>>sum;
	rub=0;
	int er=0;
	//out<<qu<<endl;
	for(i=1;i<=qu;i++)
	{
		if(i!=start&&way[start][i]!=99999999)
		{
			er++;
			v[er]=way[start][i];
			we[er]=w[i];
		}
	}
	for(i=1;i<=er;i++)
	{
		for(j=sum;j>=v[i];j--)
		{
		    if(f[j-v[i]]+we[i]>f[j])f[j]=f[j-v[i]]+we[i];
		}
	}
	out<<f[sum]%10000007<<endl;
	in>>q;
	for(i=1;i<=q;i++)
	{
		string x1,x2;
		int rub1,rub2;
		in>>x1>>x2;
		rub1=F[find(change[x1])];
		rub2=F[find(change[x2])];
		if(way[rub1][rub2]!=0&&way[rub1][rub2]!=99999999)
		{
			out<<way[rub1][rub2]<<endl;
		}
		else out<<-1<<endl;
	}
	in.close();
	out.close();
	return 0;
}