#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define inf 10000000000000
#define maxn 50005
struct EDGE{

    int end;
    int weight;
    int next;
}edge[maxn*2];
int head[maxn*2];
int price[maxn];
long long dis[maxn];
bool vis[maxn];

int e,v;


void spfa(){
    queue <int> q;
    memset(vis,0,sizeof(vis));
    for(int i=0 ; i<=e ; i++)
        dis[i]=inf;
    dis[1]=0;
    vis[1]=true;
    q.push(1);
    while(!q.empty()){

        int now=q.front();
        q.pop();
        vis[now]=true;
        for(int i=head[now] ; i ; i=edge[i].next)
            if(dis[edge[i].end] > dis[now] + edge[i].weight){
                dis[edge[i].end] = dis[now] + edge[i].weight;
                if(!vis[edge[i].end]){
                    vis[edge[i].end]=true;
                    q.push(edge[i].end);
                }
            }
    }
}

int main(){
    int test;
    scanf("%d",&test);
    while(test--){

        int a,b,w;
        scanf("%d%d",&e,&v);
        memset(price,0,sizeof(price));
        memset(head,0,sizeof(head));
        for(int i=1 ; i<=e ; i++)
            scanf("%d",&price[i]);
        int cnt=1;
        for(int i=0 ; i<v ; i++){

            scanf("%d%d%d",&a,&b,&w);
            edge[cnt].end=b;
            edge[cnt].weight=w;
            edge[cnt].next=head[a];
            head[a]=cnt++;
            edge[cnt].end=a;
            edge[cnt].weight=w;
            edge[cnt].next=head[b];
            head[b]=cnt++;
        }
        if(e==0||e==1) {
            printf("0\n");
            continue;
        }
        spfa();
        bool flag=true;
        long long res=0;
        for(int i=2 ; i<=e ; i++){

            if(dis[i]==inf){

                flag=false;
                break;
            }
            res += price[i]*dis[i];
        }

        if(flag)
            printf("%lld\n",res);
        else
            printf("No Answer\n");

    }
    return 0;
}

• Re:有没有哪位大神愿意看一下这段代码哪里有问题啊？wa到吐……不胜感激 (2226) pxskdxg 2020-09-12 16:18:16