#include <cstdio>

const long MaxN=50000;
const long MaxM=50000;

struct node {
  long a,m;       
};

long T;

node heap[2*MaxM];
long count;

long N,M;
long min[MaxN],head[MaxN],minpoint;
long point[MaxM*2],next[MaxM*2],dis[MaxM*2];

long cost[MaxN],weight[MaxN];
__int64 ans;
bool noanswer;

void Open() {
  freopen ("3013.in","r",stdin);
  freopen ("3013.out","w",stdout);     
} 

void Close() {
  fclose(stdin);
  fclose(stdout);     
}

inline void swap(long a,long b) {
  node temp;
  temp=heap[a]; heap[a]=heap[b]; heap[b]=temp;
}

inline long Min(long a,long b) {
  if (heap[a].a<heap[b].a) return a;
  return b;
}

void Up(long k) {
  long f,t;
  f=(k-1)/2;
  while (k!=0) {
    t=Min(f,k);
    if (t==f) break;
    swap(k,f); k=f;
  }
}

void Down(long k) {
  long l,r,t;
  while (1) {
    l=k*2+1; r=k*2+2;
    if (l>=count) break;
    if (r>=count) t=Min(k,l); else t=Min(k,Min(l,r));
    if (t==k) break;
    swap(k,t); k=t;
  }
}

void Dijkstra_Heap() {
  long i,j; minpoint=0;
  for (i=0;i<N;i++) min[i]=-1; min[0]=0;
  count=0; i=0;
  while (min[minpoint]>=0&&i<=N) {
    j=head[minpoint];
    while (j!=-1) {
      if (min[minpoint]+dis[j]<min[point[j]]||min[point[j]]==-1) {
        min[point[j]]=min[minpoint]+dis[j];
        heap[count].a=min[point[j]]; heap[count].m=point[j]; count++;
        Up(count-1);
      } j=next[j];
    }
    cost[minpoint]=min[minpoint];
    min[minpoint]=-2; minpoint=heap[0].m;
    while (min[minpoint]==-2&&count>0) {
      heap[0]=heap[--count]; Down(0);
      minpoint=heap[0].m;
    }
    i++;
  }
}

void init() {
  long i,a,b,c,tcount=0;
  scanf ("%ld%ld",&N,&M);
  for (i=0;i<N;i++) head[i]=-1;
  for (i=0;i<2*M;i++) next[i]=-1;
  count=0; ans=0; noanswer=false;
  for (i=0;i<N;i++) scanf ("%ld",&weight[i]);
  for (i=0;i<M;i++) {
    scanf ("%ld%ld%ld",&a,&b,&c); a--; b--;
    if (a==b) continue;
    point[tcount]=b; next[tcount]=head[a]; dis[tcount]=c; head[a]=tcount++;
    point[tcount]=a; next[tcount]=head[b]; dis[tcount]=c; head[b]=tcount++;
  }
}

void work() {
  long i; __int64 a,b,c;
  for (i=0;i<N;i++) cost[i]=-1;
  Dijkstra_Heap();
  for (i=0;i<N;i++) if (cost[i]==-1) {noanswer=true; return;}
  for (i=0;i<N;i++) {
    a=cost[i]; b=weight[i]; c=a*b;
    ans+=c;
  }
}

void output() {
  if (noanswer) printf ("No Answer\n");
  else printf ("%I64d\n",ans);
}

int main() {
//  Open();
  scanf ("%ld",&T);
  for (;T>0;T--) {
    init();
    work();
    output();    
  }
//  Close();
  return 0;
}

• Re:太多了，反正我是用unsigned _int64 过的…… (2857) byron 2006-10-25 22:36:14