记录编号	40972	评测结果	AA
题目名称	[咲 -Saki-] 一起进军全国吧	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2012-07-19 21:17:56	内存使用	0.37 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cctype>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
const int MAXN=1000;
int N,top=0;
string str;
map<string,int> hash;

class line
{
	public:
		int eki;
		double dist;
}L[MAXN];
vector<int> mat[MAXN];
vector<double> val[MAXN];
queue<int> q;
int query[MAXN];

inline void Lclear()
{
	for(int i=0;i<=900;i++)
		L[i].eki=0,L[i].dist=double(0);
}

inline void InitQuery()
{
	cin>>N>>str;
	hash[str]=++top;
	for(int i=1;i<=N;i++)
	{
		cin>>str;
		if(hash[str]==0)
			hash[str]=++top;
		query[i]=hash[str];
	}
}

char strst[MAXN];
char name[MAXN];
string strtmp;
string strtt;

inline double aabs(double a)
{
	return a<0?-a:a;
}

inline void ReadLine()
{
	bool flag=false;
	int now=0; char c;
	double xxx;
	getline(cin,strtt);
	getline(cin,strtt);
	while(getline(cin,strtt))
	{
		if(strtt=="") continue;
		memset(strst,0,sizeof(strst));
		memset(name,0,sizeof(name));
		strcpy(strst,strtt.data());
		if(strst[0]=='S')
		{
			if(!flag)
			{
				flag=true;
				continue;
			}
			for(int i=1;i<=now;i++)
			{
				for(int j=i+1;j<=now;j++)
				{
					if(L[i].eki==L[j].eki) continue;
					mat[L[i].eki].push_back(L[j].eki);
					mat[L[j].eki].push_back(L[i].eki);
					val[L[i].eki].push_back(aabs(L[j].dist-L[i].dist));
					val[L[j].eki].push_back(aabs(L[j].dist-L[i].dist));
				}
			}
			Lclear();
			now=0;
			continue;
		}
		c=strst[0];
		if(isdigit(c))
		{
			sscanf(strst,"%lf %s",&xxx,name);
			strtmp=name;
			if(hash[strtmp]==0) hash[strtmp]=++top;
			L[++now]=(line){hash[strtmp],xxx};
		}
		else 
		{
			sscanf(strst,"%s %lf",name,&xxx);
			strtmp=name;
			if(hash[strtmp]==0) hash[strtmp]=++top;
			L[++now]=(line){hash[strtmp],xxx};
		}
	}
	for(int i=1;i<=now;i++)
	{
		for(int j=i+1;j<=now;j++)
		{
			if(L[i].eki==L[j].eki) continue;
			mat[L[i].eki].push_back(L[j].eki);
			mat[L[j].eki].push_back(L[i].eki);
			val[L[i].eki].push_back(aabs(L[j].dist-L[i].dist));
			val[L[j].eki].push_back(aabs(L[j].dist-L[i].dist));
		}
	}
}

int u,v; double cc;
double dist[1000];
int flag[1000];
int times[MAXN];

inline void SPFA()
{
	for(int i=1;i<=top;i++)
		dist[i]=10000000.00,flag[i]=0;
	q.push(1); flag[1]=1; dist[1]=0;
	while(q.size())
	{
		u=q.front(); q.pop(); flag[u]=0;
		for(unsigned int i=0;i<mat[u].size();i++)
		{
			v=mat[u][i];
			cc=dist[u]+val[u][i];
			if(cc>=dist[v]-0.0001) continue;
			dist[v]=cc;
			if(flag[v] ) continue;
			q.push(v);  
			flag[v]=1;
		}
	} 
	
	
	for(int i=1;i<=N;i++)
	{
		if(dist[query[i]]!=10000000.00)
			printf("%.2lf\n",dist[query[i]]);
		else printf("-1.00\n");
	}
}

int main()
{
	freopen("zengokuhe.in","r",stdin);
	freopen("zengokuhe.out","w",stdout);
	InitQuery();
	ReadLine();
	SPFA();
	return 0;
}