> #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我看一下哪里错了我靠 (30) busy12377 2009-08-11 16:22:18