2326.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
#include<string.h>

const int MAXN=1005;
double graph[MAXN][MAXN];
char s[MAXN][100];
int cover[MAXN];
int main()
{
	int i,j,k;
	int i1,i2;
	double dis,ans,d;
	int n;
	int m;
	char s1[100],s2[100];
	char t1[100],t2[100];
	scanf("%lf",&dis);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%s",s[i]);
	scanf("%d",&m);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			graph[i][j]=-1.0;
	for(i=1;i<=m;i++)
	{
		scanf("%s%s%lf",s1,s2,&d);
		for(i1=1;i1<=n;i1++)if(strcmp(s1,s[i1])==0)break;
		for(i2=1;i2<=n;i2++)if(strcmp(s2,s[i2])==0)break;
		graph[i1][i2]=d;graph[i2][i1]=d;
	}
	memset(cover,0,sizeof(cover));
	ans=0.0;
	cover[1]=1;
	for(k=1;k<n;k++)
	{
		d=10000000000.0;
		int f1,f2;
		for(i=1;i<=n;i++)if(cover[i]==1)
			for(j=1;j<=n;j++)if(cover[j]!=1)
				if(graph[i][j]!=-1)
				{
					if(graph[i][j]<d)
					{
						d=graph[i][j];
						f1=i;
						f2=j;
					}
				}
		cover[f2]=1;
		ans+=d;
	}
	if(ans<dis)
	printf("Need %.1lf miles of cable\n",ans);
	else
		printf("Not enough cable\n");
}