记录编号	40908	评测结果	PP
题目名称	[咲 -Saki-] 一起进军全国吧	最终得分	65
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	0.003 s
提交时间	2012-07-19 15:32:48	内存使用	0.51 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
using namespace std;
string w[5000];
string wen[5000];
int number,sc=1;
vector<int>a[5000];
vector<double>b[5000];
double ans[5000]={0};
bool used[5000]={0};
void spfa();
int main()
{
	freopen ("zengokuhe.in","r",stdin);
	freopen ("zengokuhe.out","w",stdout);
	cin>>number>>w[0];
	for (int i=0;i<number;i++)
	{
		cin>>wen[i];
	}
	scanf("\n");
	char q[1000];
	int ji=0;
	double qnum=0;
	while (gets(q))
	{
		int lq,tou;
		lq=strlen(q);
		if (q[0]=='S'&&q[1]==' ')
		{
			ji=0;
			continue;
		}
		if (q[0]>='0'&&q[0]<='9')
		{
			int i=0,u=0;
			double num1=0,num2=0,num=0;
			while (q[i]!=' '&&i<lq)
			{
				if (q[i]=='.')
				{
					u=1;
					i++;
					continue;
				}
				if (u==0)
				{
					num1*=10;
					num1+=(q[i]-'0');
					i++;
					continue;
				}
				if (u==1)
				{
					num2+=(q[i]-'0');
					num2/=10;
					i++;
					continue;
				}
			}
			num=num1+num2;
			string str;
			i++;
			while (q[i]!=' '&&i<lq)
			{
				str+=q[i];
				i++;
			}
			bool use=0;
			for (int j=0;j<sc;j++)
			{
				if (str==w[j])
				{
					if (ji==0)
					{
						tou=j;
						qnum=0;
					}
					else
					{
						a[tou].push_back(j);
						b[tou].push_back(num-qnum);
						a[j].push_back(tou);
						b[j].push_back(num-qnum);
						qnum=num;
						tou=j;
					}
					use=1;
					break;
				}
			}
			if (!use)
			{
				if (ji==0)
				{
					tou=sc;
					qnum=0;
				}
				else
				{
					a[tou].push_back(sc);
					b[tou].push_back(num-qnum);
					a[sc].push_back(tou);
					b[sc].push_back(num-qnum);
					qnum=num;
					tou=sc;
				}
				w[sc]=str;
				sc++;
			}
		}
		else
		{
			int i=0,u=0;
			double num1=0,num2=0,num=0;
			string str;
			while (q[i]!=' '&&i<lq)
			{
				str+=q[i];
				i++;
			}
			i++;
			while (q[i]!=' '&&i<lq)
			{
				if (q[i]=='.')
				{
					u=1;
					i++;
					continue;
				}
				if (u==0)
				{
					num1*=10;
					num1+=(q[i]-'0');
					i++;
					continue;
				}
				if (u==1)
				{
					num2+=(q[i]-'0');
					num2/=10;
					i++;
					continue;
				}
			}
			num=num1+num2;
			bool use=0;
			for (int j=0;j<sc;j++)
			{
				if (str==w[j])
				{
					if (ji==0)
					{
						tou=j;
						qnum=0;
					}
					else
					{
						a[tou].push_back(j);
						b[tou].push_back(num-qnum);
						a[j].push_back(tou);
						b[j].push_back(num-qnum);
						qnum=num;
						tou=j;
					}
					use=1;
					break;
				}
			}
			if (!use)
			{
				if (ji==0)
				{
					tou=sc;
					qnum=0;
				}
				else
				{
					a[tou].push_back(sc);
					b[tou].push_back(num-qnum);
					a[sc].push_back(tou);
					b[sc].push_back(num-qnum);
					qnum=num;
					tou=sc;
				}
				w[sc]=str;
				sc++;
			}
		}
		ji++;
	}
	/*for (int i=0;i<sc;i++)
	{
		cout<<w[i]<<endl;
		for (int j=0;j<a[i].size();j++)
		{
			cout<<w[a[i][j]]<<' '<<b[i][j]<<endl;
		}
	}*/
	spfa();
	for (int i=0;i<number;i++)
	{
		int ue=0;
		for (int j=0;j<sc;j++)
		{
			if (wen[i]==w[j])
			{
				ue=1;
				if (ans[j]==100000000)
				{
					cout<<"-1.00"<<endl;
					break;
				}
				printf("%.2lf\n",ans[j]);
				break;
			}
		}
		if (!ue)
		{
			cout<<"-1.00"<<endl;
		}
	}
	return 0;
}
void spfa()
{
	for (int i=0;i<sc;i++)
	{
		ans[i]=100000000;
	}
	int tou=0,wei=0;
	int na[1000];
	na[tou]=0;
	ans[tou]=0;
	used[0]=1;
	while (tou<=wei)
	{
		for (int i=0;i<a[na[tou]].size();i++)
		{
			int j;
			j=a[na[tou]][i];
			if (ans[j]>ans[na[tou]]+b[na[tou]][i]&&!used[j])
			{
				wei++;
				na[wei]=j;
				ans[j]=ans[na[tou]]+b[na[tou]][i];
				used[j]=1;
			}
			if (ans[j]>ans[na[tou]]+b[na[tou]][i]&&used[j])
			{
				ans[j]=ans[na[tou]]+b[na[tou]][i];
			}
		}
		tou++;
	}
}