SHknife found a problem at Children

输入格式

There are multiple test cases. For each test case, the first line contains two integers N, M (1<=N<=2000,1<=M<=100000), where N is the number of places and M is the number of two ways roads. The next M lines have Two Strings and One num in each line, like DOMITOTY YINDIN 2, which means the width of the road between DOMITOTY and YINDIN is 2. The String should always be capitalize character, and the width is in the range 1~1000000.

The last line of each case contains two strings which are the start place and the destination of SHknife. You can assuem all the length of each String will be less than or equal with 20.

输出格式

For each test case, just output a line containing an integer, which is the width of the widest path from the start place to the destination.

Output -1 if there is no solution.

样例输入

3 2 
DOMITERY YINDING 3
YINDING OFFICE 4
DOMITERY OFFICE

样例输出

3

SPFA

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using  namespace  std;
const  int M=10001;
struct  hlb {
	unsigned  long  rate;
	char  s[30];
	int p;
	hlb *next;
}*hash[M];
struct  lb {
	int u,v,w;
} date[1000010];
char  sa[30],sb[30];
int w,num,n,m;
int f[2010],rank[2010];

int shash( char  *key) {
	unsigned   long  h=0;
	while(*key) {
		h=(h<<4)+*key++;
		unsigned  long  g=h & 0Xf0000000L;
		if (g) h^=g>>24;
		h&=~g;
	}
	return  h;
}
bool  comp(lb a,lb b) {
	return  a.w>b.w;   //宽度由大到小排序
}
int hfind( char  *s) {
	unsigned   long  k=shash(s);
	int d=k%M;
	hlb *pt;
	pt=hash[d];
	while(pt) {
		if (pt->rate==k&&strcmp(pt->s,s)==0) return  pt->p;
		pt=pt->next;
	}
	pt=new  hlb;
	pt->rate=k;
	pt->p=++num;
	strcpy(pt->s,s);
	pt->next=hash[d];
	hash[d]=pt;
	return  num;
}
int ff(int k) {
	if (k!=f[k])f[k]=ff(f[k]);
	return  f[k];
}
void  uno(int i, int j) {
	if (ff(i)==ff(j)) return ;
	if (rank[f[i]]<=rank[f[j]]) {
		if (rank[f[i]]==rank[f[j]])rank[f[j]]++;
		f[f[i]]=f[j];
	} else   f[f[j]]=f[i];
}
int main() {
	int i,a,b,start,over;
	while(scanf("%d%d",&n,&m)==2) {
		if (m>1000000) while(1);
		memset(hash,0,sizeof(hash));
		num=0;
		for(i=1; i<=m; i++) {
			scanf("%s%s%d",sa,sb,&date[i].w);
			date[i].u=hfind(sa);
			date[i].v=hfind(sb);
			if (num>n||num>2000)while(1);
		}
		scanf("%s%s",sa,sb);
		start=hfind(sa);
		over=hfind(sb);
		sort(date+1,date+1+m,comp);
		for(i=1; i<=n; i++)f[i]=i;
		memset(rank,0,sizeof(rank));
		for(i=1; i<=m; i++) {
			uno(date[i].u,date[i].v);
			if (ff(start)==ff(over)) {
				printf("%d\n",date[i].w);
				break;
			}
		}
		if (i>m)printf("-1\n");
	}
	return  0;
}