记录编号	41115	评测结果	PT
题目名称	[咲 -Saki-] 一起进军全国吧	最终得分	44
用户昵称	Truth.Cirno	是否通过	未通过
代码语言	C++	运行时间	1.001 s
提交时间	2012-07-20 16:49:25	内存使用	31.01 MiB

#include <cstdio>
#include <cstring>
#include <memory.h>
using namespace std;

const int MAXINT=100000000;

struct strings
{
	char s[100];
};

double map[2000][2000],cost[2000];
bool used[2000];
strings city[1000],que[1000];

int main(void)
{
	freopen("zengokuhe.in","r",stdin);
	freopen("zengokuhe.out","w",stdout);
	int i,j,n,c,len,pp,frompos,topos,citynum=0,minpos;
	double minnum,dis[1000];
	bool found;
	strings str[100],strdis[100],from,temp;
	scanf("%d %s\n",&n,&city[1].s);
	citynum=1;
	for (i=1;i<=n;i++)
		scanf("%s\n",que[i].s);
	while (scanf("%s%*[^\n]\n",&str[0].s)==1)
	{
		memset(dis,0,sizeof(dis));
		c=0;
		scanf("%s",&str[c].s);
		while (str[c].s[0]!='S'&&str[c].s[0]!='\0')
		{
			scanf("%s%*[^\n]\n",&strdis[c++].s);
			scanf("%s",&str[c].s);
		}
		for (i=0;i<c;i++)
		{
			if (str[i].s[0]>='0'&&str[i].s[0]<='9')
			{
				temp=str[i];
				str[i]=strdis[i];
				strdis[i]=temp;
			}
		}
		for (i=0;i<c;i++)
		{
			found=false;
			for (j=1;j<=citynum;j++)
				if (strcmp(str[i].s,city[j].s)==0)
				{
					found=true;
					break;
				}
			if (!found)
				city[++citynum]=str[i];
		}
		for (i=0;i<c;i++)
		{
			len=strlen(strdis[i].s);
			pp=len;
			for (j=0;j<len;j++)
			{
				if (strdis[i].s[j]!='.')
					dis[i]=dis[i]*10+strdis[i].s[j]-'0';
				else
					pp=j;
			}
			for (j=len-pp-1;j>=1;j--)
				dis[i]/=10;
		}
		for (i=0;i<c;i++)
		{
			if (dis[i]==0)
				from=str[i];
		}
		for (i=1;i<=citynum;i++)
		{
			if (strcmp(city[i].s,from.s)==0)
			{
				frompos=i;
				break;
			}
		}
		for (i=0;i<c;i++)
		{
			if (dis[i]==0)
				continue;
			for (j=1;j<=citynum;j++)
				if (strcmp(city[j].s,str[i].s)==0)
				{
					topos=j;
					break;
				}
			if (dis[i]<map[frompos][topos]||map[frompos][topos]==0)
			{
				map[frompos][topos]=dis[i];
				map[topos][frompos]=dis[i];
				if (frompos==1)
					cost[topos]=dis[i];
				if (topos==1)
					cost[frompos]=dis[i];
			}
		}
	}
	for (i=2;i<=citynum;i++)
		if (cost[i]==0)
			cost[i]=MAXINT;
	for (i=1;i<=citynum;i++)
		for (j=1;j<=citynum;j++)
			if (i!=j&&map[i][j]==0)
				map[i][j]=MAXINT;
	used[1]=true;
	c=citynum-1;
    while (c)
    {
		minnum=MAXINT;
		for (i=1;i<=citynum;i++)
			if (!used[i]&&minnum>cost[i])
			{
				minnum=cost[i];
				minpos=i;
			}
        for (i=1;i<=citynum;i++)
            if (!used[i]&&i!=minpos)
                if (cost[i]>cost[minpos]+map[minpos][i])
                    cost[i]=cost[minpos]+map[minpos][i];
        used[minpos]=true;
		c--;
    }
	for (i=1;i<=n;i++)
	{
		found=false;
		for (j=1;j<=citynum;j++)
		{
			if (strcmp(city[j].s,que[i].s)==0)
			{
				found=true;
				if (cost[j]>=MAXINT)
					printf("-1.00\n");
				else
					printf("%.2lf\n",cost[j]);
				break;
			}
		}
		if (!found)
			printf("-1.00\n");
	}
	return(0);
}