#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 205
#define MAXL 35
#define MOD 1023
#define INF (1<<30)
int n,m,x=0,top,ncity,w[MAXN][MAXN],d[MAXN];	//x为case的编号
bool visit[MAXN];
struct Hash{
	char s[MAXL];
	int city,next;
} hash[MOD<<1];
int flag[MOD<<1]={0};

int Insert(char *str){		//兼插入和查找与一体
	int i=0,k=0;	//把一个字符串映射成各个字母的ASCII码加起来
	while (str[i])	k+=str[i++];

	if (flag[k]!=x){	//直接插入
		flag[k]=x;
		hash[k].next=-1;
		hash[k].city=ncity++;
		strcpy(hash[k].s , str);
		return ncity-1;
	}

	while (hash[k].next!=-1){
		if (strcmp(hash[k].s , str)==0 )		return hash[k].city;
		k=hash[k].next;
	}
	if (strcmp(hash[k].s , str)==0 )		return hash[k].city;
	hash[k].next = ++top;
	strcpy(hash[top].s , str);
	hash[top].city=ncity++;
	hash[top].next=-1;
	return ncity-1;
}

void Prim(int s, int e){
	int i,j,k,maxd,ans=INF;
	for (i=0;i<ncity;++i){
		visit[i]=false;
		d[i]=w[s][i];
	}
	visit[s]=true;
	for (i=1;i<n;++i){
		for (maxd=-INF,j=0;j<n;++j)
			if (!visit[j] && d[j]>maxd)		maxd=d[k=j];
		visit[k]=true;
		if (ans>d[k])	ans=d[k];
		if (k==e)	break;
		for (j=0;j<n;++j)
			if (!visit[j] && d[j]<w[k][j] )		d[j]=w[k][j];
	}
	printf("%d tons\n\n", ans);
}


int main(){
	char st[MAXL],ed[MAXL];
	int i,j,a,b,c;
	while (scanf("%d %d", &n, &m)!=EOF && m){
		++x;
		printf("Scenario #%d\n", x);

		top=MOD;
		ncity=0;
		for (i=0;i<n;++i)
			for (j=0;j<n;++j)
				w[i][j] = w[j][i] = -INF;

		for (i=0;i<m;++i){
			scanf("%s %s %d",st, ed, &c);
			a=Insert(st);
			b=Insert(ed);
			w[a][b] = w[b][a] = c;
		}

		scanf("%s %s", st, ed);
		Prim(Insert(st), Insert(ed));
	}
	return 0;
}

• Re:一不小心0ms刷进第一版……好开心~ (31) Ruby931031 2012-09-07 15:55:15