#include <stdio.h>
#include <string.h>
typedef struct arcNode
{
	int son,dif;
	struct arcNode *next;
}arcNode;
typedef struct
{
	char name[128];
	int age;
	struct arcNode *next;
}Node;
typedef struct List
{
	char *name;
	struct List *next;
}List;
Node d[128];
List a[128];
bool flag[128];
int pos,start;
void init()
{
	for(int i=0;i<128;i++)
	{
		d[i].next=NULL;
		a[i].name="";
		a[i].next=NULL;
	}
}
int locate(char *s)
{
	int i;
	for(i=0;i<pos;i++)
		if(strcmp(s,d[i].name)==0)
			return i;
	strcpy(d[pos].name,s);
	if(strcmp(s,"Ted")==0)
	{
		d[pos].age=100;
		start=pos;
	}
	pos++;
	return pos-1;
}
//桶排+插入排序。
void insert(int x)
{
	int index=d[x].age;
	List *p=&a[index],*q,*ptr;
	while(p&&strcmp(p->name,d[x].name)<0)
	{
		q=p;
		p=p->next;
	}
	ptr=new List;
	ptr->name=d[x].name;
	ptr->next=q->next;
	q->next=ptr;
}
//从ted开始ＤＦＳ．
void DFS(int x)
{
	flag[x]=true;
	insert(x);　　　　　　　　//插入桶中。
	for(arcNode *p=d[x].next;p;p=p->next)
		if(!flag[p->son])
		{
			d[p->son].age=d[x].age-p->dif;
			DFS(p->son);
		}
}
int main()
{
	int t,i,differ,n,c=0,px,py;
	arcNode *ptr;
	char fn[128],sn[128];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		init();
		for(pos=i=0;i<n;i++)
		{
			scanf("%s%s%d",fn,sn,&differ);
			px=locate(fn);
			py=locate(sn);
			ptr=new arcNode;
			ptr->son=py;
			ptr->dif=differ;
			ptr->next=d[px].next;
			d[px].next=ptr;
		}
		DFS(start);
		printf("DATASET %d\n",++c);
		for(i=99;i>0;i--)
		{
			List *pt=a[i].next;
			while(pt)
			{
				printf("%s %d\n",pt->name,i);
				pt=pt->next;
			}
		}
		memset(flag,false,sizeof(flag));
	}
	return 0;
}

• Re:一直wa,测试了许多例子都没出错,晕,哪位大牛路过看下，谢啦! (23) a024014 2007-04-02 12:00:31
• Re:一直wa,测试了许多例子都没出错,晕,哪位大牛路过看下，谢啦! (1903) try99 2007-05-29 08:11:58
  • Re:一直wa,测试了许多例子都没出错,晕,哪位大牛路过看下，谢啦! (45) try99 2007-05-29 08:13:15
    • 偶也是..bfs.被sort给整了 (55) crackerwang 2007-09-20 11:40:15
    • Re:一直wa,测试了许多例子都没出错,晕,哪位大牛路过看下，谢啦! (55) JLKJ_ZHUSHAN 2010-07-28 15:24:57