记录编号	129701	评测结果	PP
题目名称	[咲 -Saki-] 一起进军全国吧	最终得分	17
用户昵称	水中音	是否通过	未通过
代码语言	C++	运行时间	0.021 s
提交时间	2014-10-20 19:25:59	内存使用	12.75 MiB

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<queue>
using namespace std;//这么麻烦的读入… 
string s1,s2,s3;
queue<int> B;
map<string,int> A;
char ch;
int n=0,m=0,zj1,zj2,zj3,i,p,be;
int to[1001][1001]={0},road[1001],im[101]={0};
double street[1001][1001]={0},roadv[1001],k1,k2,zui[1001];
bool flag[1001][1001]={0};
void work()
{
	for(i=2;i<=road[0];i++)
	{
		if(!flag[ road[1] ][ road[i] ])
		{
			flag[ road[1] ][ road[i] ]=true;
			flag[ road[i] ][ road[1] ]=true;
			to[ road[1] ][0]++;
			to[ road[1] ][ to[ road[1] ][0] ]=road[i];
			to[ road[i] ][0]++;
			to[ road[i] ][ to[ road[i] ][0] ]=road[1];
			street[ road[1] ][ road[i] ]=roadv[i];
			street[ road[i] ][ road[1] ]=roadv[i];
		}
		else
		{
			if(roadv[i]<street[ road[1] ][ road[i] ])
			{
				street[ road[1] ][ road[i] ]=roadv[i];
				street[ road[i] ][ road[1] ]=roadv[i];
			}
		}
	}
	for(i=3;i<=road[0];i++)
	for(p=2;p<i;p++)
	{
		if(!flag[ road[i] ][ road[p] ])
		{
			flag[ road[i] ][ road[p] ]=true;
			flag[ road[p] ][ road[i] ]=true;
			to[ road[i] ][0]++;
			to[ road[i] ][ to[ road[i] ][0] ]=road[p];
			to[ road[p] ][0]++;
			to[ road[p] ][ to[ road[p] ][0] ]=road[i];
			k2=roadv[i]-roadv[p];
			if(k2<0) k2*=-1;
			street[ road[p] ][ road[i] ]=k2;
			street[ road[i] ][ road[p] ]=k2;
		}
		else
		{
			k2=roadv[i]-roadv[p];
			if(k2<0)k2*=-1;
			if(k2<street[ road[i] ][ road[p] ])
			{
				street[ road[i] ][ road[p] ]=k2;
				street[ road[p] ][ road[i] ]=k2;
			}
		}
	}
}
void change()
{
	zj1=ch-48;
	ch=getchar();
	while(ch!='.'&&ch!=' '&&ch!='\n')
	{
		zj1*=10;
		zj1+=ch-48;
		ch=getchar();
	}
	k1=0;
	if(ch=='.')
	{
		zj2=0;
		ch=getchar();
		while(ch!=' '&&ch!='\n')
		{
			zj2*=10;
			zj2+=ch-48;
			ch=getchar();
		}
		k1=zj2;
		while(k1>=1)k1/=10;
	}
	k1+=zj1;
}
void rechange()
{
	ch=getchar();
	while(ch!=' '&&ch!='\n')
	{
		s1+=ch;
		ch=getchar();
	}
	if(!A[s1]){m++;A[s1]=m;}
}
void init()
{
	ch=getchar();
	while(ch<='0'||ch>='9')ch=getchar();
	n=0;
	while(ch!=' '){n*=10;n+=ch-48;ch=getchar();}
	rechange();
	be=A[s1];
	for(i=1;i<=n;i++)
	{
		s1.erase(0,1000);
		rechange();
		im[i]=A[s1];
	}
	while((ch=getchar())!=EOF)
	{
		if(ch=='\n'||ch==' ')continue;
		if(ch>='0'&&ch<='9')
		{
			change();
			s1.erase(0,1000);
			while(ch==' ') ch=getchar();
			s1+=ch;						
			rechange();
			if(k1>=0)
			{
				road[0]++;
				road[ road[0] ]=A[s1];
				roadv[ road[0] ]=k1;
			}
			while(ch!='\n') ch=getchar();
		}
		else
		{
			if(ch!='S')
			{
				s1.erase(0,1000);
				s1+=ch;
				rechange();
				while(ch==' ') ch=getchar();
				change();
				if(k1>=0)
				{
					road[0]++;
					road[ road[0] ]=A[s1];
					roadv[ road[0] ]=k1;
				}
				while(ch!='\n') ch=getchar();
				continue;
			}
			else
			{
				while(ch!='\n')ch=getchar();
				ch=getchar();
				if(ch>='0'&&ch<='9')
				{
					change();
					s1.erase(0,1000);
					rechange();
					while(ch!='\n') ch=getchar();
				}
				else
				{
					s1.erase(0,1000);
					s1+=ch;
					rechange();
					while(ch==' ') ch=getchar();
					change();
					while(ch!='\n') ch=getchar();
				}
				if(k1!=0)
				{
					road[0]++;
					road[ road[0] ]=A[s1];
					roadv[ road[0] ]=k1;
				}
				else
				{
					work();
					road[0]=1;
					road[1]=A[s1];
					roadv[ road[0] ]=k1;
				}
			}
		}
	}
	work();
} 
void SPFA()
{
	for(i=1;i<=m;i++) zui[i]=1e10;
	zui[be]=0;
	for(i=1;i<=to[be][0];i++)
	{
		B.push( to[be][i] );
		zui[ to[be][i] ]=street[be][ to[be][i] ];
	}
	while(!B.empty())
	{
		zj1=B.front();B.pop();
		for(i=1;i<=to[zj1][0];i++)
		{
			k1=zui[zj1]+street[zj1][ to[zj1][i] ];
			if(k1<zui[ to[zj1][i] ])
			{
				zui[ to[zj1][i] ]=k1;
				B.push(to[zj1][i]);
			}
		}
	}
}
int main()
{
	freopen("zengokuhe.in","r",stdin);
	freopen("zengokuhe.out","w",stdout);
	init();
	SPFA();
	for(i=1;i<=n;i++)
	{
		if(zui[im[i]]==1e10) printf("-1.00\n");
		else printf("%.2lf\n",zui[im[i]]);
	}
	return 0;
}