#include <stdio.h>
#include <stdlib.h>

#define MAX 1000010
#define LEN 2000020

typedef struct eadge eadge_t;
struct eadge
{
	long stop;
	long distance;
	eadge_t* next;
};
eadge_t out_eadges[MAX];
eadge_t in_eadges[MAX];

void init_link();
void free_link();
void insert_link(eadge_t* root, eadge_t* et);

long val[MAX];

long queue[LEN];
long head, tail;
void Insert(long num);
long Get();
long Is_Empty();
long Find(long num);

void Ini(long p);
int main(void)
{
	long n, p, q, i, num, sour, dest, distance;
	long long result;
	eadge_t* et = NULL;
	scanf("%d", &n);
	while(n --)
	{
		scanf("%ld%ld", &p, &q);
		init_link();
		for(i = 0; i < q; i ++)
		{
			scanf("%ld%ld%ld", &sour, &dest, &distance);
			et = (eadge_t*)malloc(sizeof(eadge_t));
			et->stop = dest;
			et->distance = distance;
			et->next = NULL;
			insert_link(&out_eadges[sour], et);

			et = (eadge_t*)malloc(sizeof(eadge_t));
			et->stop = sour;
			et->distance = distance;
			et->next = NULL;
			insert_link(&in_eadges[dest], et);
		}
		Ini(p);
		Insert(1);
		while(!Is_Empty())
		{
			num = Get();
			et = out_eadges[num].next;
			while(et != NULL)
			{
				if(val[et->stop] > val[num] + et->distance)
				{
					val[et->stop] = val[num] + et->distance;
					if(!Find(et->stop))
						Insert(et->stop);
				}
				et = et->next;
			}
		}
		for(i = 1, result = 0; i < p + 1; i ++)
			result += val[i];

		Ini(p);
		Insert(1);
		while(!Is_Empty())
		{
			num = Get();
			et = in_eadges[num].next;
			while(et != NULL)
			{
				if(val[et->stop] > val[num] + et->distance)
				{
					val[et->stop] = val[num] + et->distance;
					if(!Find(et->stop))
						Insert(et->stop);
				}
				et = et->next;
			}
		}
		for(i = 1; i < p + 1; i ++)	
			result += val[i];

		printf("%lld\n", result);
		free_link();

	}
	return 0;
}

void init_link()
{
	long i = 0;
	for(i = 1; i < MAX; i ++)
	{
		out_eadges[i].next = NULL;
		in_eadges[i].next = NULL;
	}
}

void free_link()
{
	long i = 0;
	eadge_t* tem = NULL;
	for(i = 1; i < MAX; i ++)
	{
		eadge_t* et = in_eadges[i].next;
		while(et != NULL)
		{
			tem = et;
			et = et->next;
			free(tem);
		}
		et = out_eadges[i].next;
		while(et != NULL)
		{
			tem = et;
			et = et->next;
			free(tem);
		}
	}
}

void insert_link(eadge_t* root, eadge_t* et)
{
	eadge_t* pt = root;
	while(pt->next != NULL)
		pt = pt->next;
	pt->next = et;
	et->next = NULL;
}

void Insert(long num)
{
	queue[tail] = num;
	tail = (tail + 1) % LEN;
}
long Get()
{
	long tem = head;
	head = (head + 1) % LEN;	
	return queue[tem];
}

long Is_Empty()
{
	if(tail == head)
		return 1;
	return 0;
}

long Find(long num)
{
	int i = 0;
	for(i = head; i != tail; i = (i + 1) % LEN)
	{
		if(queue[i] == num)
			return 1;
	}
	return 0;
}

void Ini(long p)
{
	long i = 0;
	val[1] = 0;
	for(i = 2; i < p + 1; i ++)
		val[i] = 1000000001;

	head = 0;
	tail = 0;
}

• Re:太坑爹了，spfa+邻接表，怎么还超时啊，跪求各路大神帮忙，在线等 (22) wocha 2012-08-20 20:34:50