#include
      
                   #include
       
         using namespace std; #define maxn 50002 const __int64 inf=(__int64)1<<63-1;        struct Edge {
     int v; int weight; int next; }Vertex[4*maxn];                            int head[maxn],curr; int cases,v,e,i,j,edge[maxn][3],w[maxn]; void add_edge(int s,int t,int w)        //新增结点不用申请空间, 跑了 579 MS {
         Vertex[curr].v=t;     Vertex[curr].weight=w;     Vertex[curr].next=head[s];     head[s]=curr++; } bool S[maxn]; __int64 distD[maxn],sum;    void spfa(int u) {
         fill(distD,distD+v+1,inf);     distD[u]=0;     memset(S,0,sizeof(S[0])*(v+1));     S[u]=1;     deque
        
          col;            col.push_back(u); while(!col.empty())     {
     int uu=col.front();         col.pop_front();         S[uu]=0; for(i=head[uu];i!=-1;i=Vertex[i].next)         {
     if(distD[uu]+Vertex[i].weight
        
       
      

　　

#include
      
                   //单源最短路SPFA     #include
       
         using namespace std; #define maxn 50002 const __int64 inf=(__int64)1<<63-1;        //inf=4611686018427387904    //(1)#define inf (1<<63)-1  (2)const __int64 inf=(__int64)(1<<63)-1;  (3)const __int64 inf=(1<<63)-1;   这三者的值都为-1 struct Edge {
     int index; int weight;     Edge *next; }Vertex[maxn];                            int cases,v,e,i,j,edge[maxn][3],w[maxn]; void add_edge(int s,int t,int w) {
         Edge *q=new Edge;        //每次都new 耗时间,跑了2391 MS     q->index=t;q->weight=w;     q->next=Vertex[s].next;Vertex[s].next=q;    //不必检查重边,直接插入即可 } bool S[maxn]; __int64 distD[maxn],sum;    //这里要声明为__int64 void spfa(int u) {
         fill(distD,distD+v+1,inf);     distD[u]=0;     memset(S,0,sizeof(S[0])*(v+1));     S[u]=1; int uu,vv,wei;     deque
        
          col;        //spfa 队列     col.push_back(u); while(!col.empty())     {
             uu=col.front();         col.pop_front();         S[uu]=0;         Edge *curr=Vertex[uu].next; while(curr!=NULL)         {
                 vv=curr->index;wei=curr->weight; if(distD[uu]+wei
         
          next;         }     } for(i=1;i<=v;++i)        if(distD[i]==inf)         {
                 printf("No Answer\n"); return ;         }     sum=0; for(i=1;i<=v;++i)         sum+=w[i]*distD[i];     printf("%I64d\n",sum); } int main() {
         scanf("%d",&cases); while(cases--)     {
             scanf("%d%d",&v,&e); for(i=1;i<=v;++i)             scanf("%d",&w[i]); for(i=1;i<=v;++i)             Vertex[i].next=NULL; for(i=1;i<=e;++i)         {
                 scanf("%d%d%d",&edge[i][0],&edge[i][1],&edge[i][2]);             add_edge(edge[i][0],edge[i][1],edge[i][2]);        //双向边             add_edge(edge[i][1],edge[i][0],edge[i][2]);         }         spfa(1);     } return 0; } /* 要注意以下情况: (1)当v=0,1时都是输出0,但不必另外加判断, 因为当v=0时,在决定是否No Answer的for循环for(i=1;i<=v;++i)本身就不会执行,sum=0 当v=1时,生成树中的根结点1的distD[1]=0,其他结点(若有的话)的distD也为0,sum+=w[i]*distD[i];sum仍然为0 (2)也不必另外筛除掉指向自己的边,因为在SPFA函数内的if(distD[v]+w
          
           index=t;q->weight=w;     Edge *tmp=Vertex[s].next;     while(tmp!=NULL&&tmp->index!=t)         tmp=tmp->next;     if(tmp==NULL)     {
             q->next=Vertex[s].next;Vertex[s].next=q;    //没找到重边     }     else         tmp->weight=min(tmp->weight,w);        //找到重边,取较小值 } 当然,如果是邻接矩阵就要判断重边了,取其中的最小值 (4)边是无向边 (5)要注意inf的取值,最短路径数组distD和结果sum 都要用__int64 存储 另外,不用deque,也可用循环队列,如下: void spfa(int u) {
         fill(distD,distD+v+1,inf);     distD[u]=0;     memset(S,0,sizeof(S[0])*(v+1));     S[u]=1;     int uu,vv,wei;     int deq[maxn],head=0,rear=1;     deq[0]=u;     while(head!=rear)    //循环队列     {
             uu=deq[head++];         if(head==maxn)             head=0;         S[uu]=0;         Edge *curr=Vertex[uu].next;         while(curr!=NULL)         {
                 vv=curr->index;wei=curr->weight;             if(distD[uu]+wei
           
            next; } } for(i=1;i<=v;++i) if(distD[i]==inf) { printf("No Answer\n"); return ; } sum=0; for(i=1;i<=v;++i) sum+=w[i]*distD[i]; printf("%I64d\n",sum); } */