这个题很有意思，其实就是求出最短路径，再用最短路径值*结点值的和。通过这题，又找到了编程的一个bug，总是想省空间，结果就只能悲剧了，还是先相乘后强制转化的问题，必须出错的！第一次用比__int64还大的数据类型usigned long long,另外熟悉了一下宏，感觉还不错。对最短路径又有了新的想法，理解算法很有好处啊！！
#include<iostream>
#include<queue>
#define MAXN 50005
#define ULL unsigned long long
#define INF 184467440737095516151
using namespace std;struct Node
{int v;ULL price;Node *next;
}Edge[MAXN<<1],*ptr[MAXN];int N,E,EdgeNum;
ULL dist[MAXN];void addEdge( int u,int v,ULL price )
{Node *p=&Edge[EdgeNum++];p->v=v;p->price=price;p->next=ptr[u];ptr[u]=p;
}
bool inQ[MAXN];
bool changed[MAXN];
void SPFA()
{memset( changed,0,sizeof(changed) );memset( inQ,0,sizeof(inQ) );memset( dist,0xFF,sizeof(dist) );dist[1]=0;queue<int>myQueue;myQueue.push(1);while( !myQueue.empty() ){int u=myQueue.front();myQueue.pop();Node *p=ptr[u];inQ[u]=false;while( p ){if( dist[p->v]>dist[u]+p->price ){dist[p->v]=dist[u]+p->price;changed[p->v]=true;if( !inQ[p->v] ){inQ[p->v]=true;myQueue.push(p->v);}}p=p->next;}}
}int main()
{int degree[MAXN];int i,j;int T;scanf( "%d",&T );while( T-- ){EdgeNum=0;scanf( "%d %d",&N,&E );for( i=1;i<=N;i++ )ptr[i]=NULL;for( i=1;i<=N;i++ )scanf( "%d",°ree[i] );int u,v;ULL price;for( i=1;i<=E;i++ ){scanf( "%d %d %llu",&u,&v,&price );addEdge( u,v,price );addEdge( v,u,price );}SPFA();unsigned long long ans=0;for( i=2;i<=N;i++ )if( changed[i]==false ){printf( "No Answer\n" );goto BY;}for( i=2;i<=N;i++ )ans+=dist[i]*degree[i];printf( "%llu\n",ans );BY:; }return 0;
}