#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int T,i,j,n,m,a,b,d;
unsigned long long dijk[50010],ans,v[50010];
bool used[50010],r;
struct point
{
	int pa,dist;
	point *next;
}p,*pi;
point tu[50010];
priority_queue<point>que;
bool operator<(point p1,point p2)
{
	return (dijk[p1.pa]>dijk[p2.pa]);
}
int main()
{
	freopen("in.txt","r",stdin);
	scanf("%d",&T);
	while (T--)
	{
		while (!que.empty()) que.pop();
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
			scanf("%llu",&v[i]);
		for(i=0;i<n;i++)
		{
			tu[i].pa=tu[i].dist=0;
			tu[i].next=NULL;
		}
		while (m--)
		{
			scanf("%d%d%d",&a,&b,&d);
			a--;b--;
			pi=new point;
			pi->next=tu[a].next;
			pi->pa=b;
			pi->dist=d;
			tu[a].next=pi;
			pi=new point;
			pi->next=tu[b].next;
			pi->pa=a;
			pi->dist=d;
			tu[b].next=pi;
		}
		for(i=0;i<n;i++) dijk[i]=1000000000000;
		memset(used,false,sizeof(used));
		dijk[0]=0;p.pa=0;p.dist=0;
		que.push(p);
		while (!que.empty())
		{
			p=que.top();
			que.pop();
			if (used[p.pa]) continue;
			used[p.pa]=true;
			pi=tu[p.pa].next;
			while (pi)
			{
				if (!used[pi->pa]&&dijk[pi->pa]>dijk[p.pa]+pi->dist)
				{
					dijk[pi->pa]=dijk[p.pa]+pi->dist;
					que.push(*pi);
				}
				pi=pi->next;
			}
		}
		ans=0;
		r=true;
		for(i=0;i<n;i++)
			if (dijk[i]==1000000000000)
			{
				r=false;break;
			}
			else ans+=dijk[i]*v[i];
		if (r) printf("%llu\n",ans);
		else printf("No Answer\n");
	}
	return 0;
}

• Re:谁帮DD我看一下哪里错了我靠 (1685) busy12377 2009-08-11 16:21:47
  • Re:谁帮DD我看一下哪里错了我靠 (30) busy12377 2009-08-11 16:22:18