#include <iostream>
#include <cstdio>
#include <queue>
#include <list>
using namespace std;
const int N=1000005;
list<long>v1[N],w1[N],v2[N],w2[N];
bool used[N];
struct node
{
	int v;
	__int64 dis;
}dd[N];
node temp;
priority_queue<node> Q;
bool operator <(const node &x,const node &y)
{
	return x.dis > y.dis;	
}
int main()
{
	int p,q,i,j,k,n,m,tt,sum,max,d,s,e,minv,w;
	scanf("%d",&tt);
	__int64 min,ans1,ans2;
	for (max=1;max<=tt;max++)
	{
		while(!Q.empty())
			Q.pop();
		ans1=ans2=0;
		scanf("%d%d",&n,&q);
		v1[1].push_back(1);
		w1[1].push_back(0);
		v2[1].push_back(1);
		w2[1].push_back(0);
		for (i=1;i<=q;i++)
		{
			scanf("%d%d%d",&s,&e,&w);
			v1[s].push_back(e);
			w1[s].push_back(w);
			v2[e].push_back(s);
			w2[e].push_back(w);
		}
		for (i=1;i<=n;i++)used[i]=0;		
		for (i=1;i<=n;i++)dd[i].v=i,dd[i].dis=1e15;
		while(!v1[1].empty())
		{
			dd[v1[1].back()].v=v1[1].back();
			dd[v1[1].back()].dis=w1[1].back();
			Q.push(dd[v1[1].back()]);
			v1[1].pop_back();
			w1[1].pop_back();		
		
		}
		used[1]=1;
		for (i=1;i<=n;i++)
		{
			while(!Q.empty())
			{
				temp=Q.top();
				Q.pop();
				if(used[temp.v]==0)break;
			}
			minv=temp.v;
			used[minv]=1;
			for (j=1;j<=n;j++)
			{
				while(!v1[minv].empty())
				{
					k=v1[minv].back();
					m=w1[minv].back();
					v1[minv].pop_back();
					w1[minv].pop_back();
					if(used[k]==0)
					{
						if(dd[k].dis>dd[minv].dis+m)
							dd[k].dis=dd[minv].dis+m;
						temp.v=k;
						temp.dis=dd[k].dis;
						Q.push(temp);
					}
				}
			}
		}
		for (i=1;i<=n;i++)
		{
				ans1+=dd[i].dis;
		}
		while(!Q.empty())
			Q.pop();
		for (i=1;i<=n;i++)used[i]=0;		
		for (i=1;i<=n;i++)dd[i].v=i,dd[i].dis=1e15;
		while(!v2[1].empty())
		{
			dd[v2[1].back()].v=v2[1].back();
			dd[v2[1].back()].dis=w2[1].back();
			Q.push(dd[v2[1].back()]);
			v2[1].pop_back();
			w2[1].pop_back();		
		
		}
		used[1]=1;
		for (i=1;i<=n;i++)
		{
			while(!Q.empty())
			{
				temp=Q.top();
				Q.pop();
				if(used[temp.v]==0)break;
			}
			minv=temp.v;
			used[minv]=1;
			for (j=1;j<=n;j++)
			{
				if(used[j]==1)continue;
				while(!v2[minv].empty())
				{
					k=v2[minv].back();
					m=w2[minv].back();
					v2[minv].pop_back();
					w2[minv].pop_back();
					if(used[k]==0)
					{
						if(dd[k].dis>dd[minv].dis+m)
							dd[k].dis=dd[minv].dis+m;
						temp.v=k;
						temp.dis=dd[k].dis;
						Q.push(temp);
					}
				}
			}
		}
		for (i=1;i<=n;i++)
		{
				ans2+=dd[i].dis;
		}
		printf("%I64d\n",ans1+ans2);
		
	}
	return 0;
}

• Re:为什么我的程序开始运行以后要等很久才能输入呢?大牛们帮忙看下被 谢谢 (18) rush_again 2008-09-15 22:58:31