图论最短路spfa--poj3013Big chrismas tree

这道题可以转换成

以1为源点求最短路

答案就是点权*dis

spfa

用的bfs

直接粘代码好了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 50005
#define LL long long
#define inf (1LL<<60)
using namespace std;
int t,n,m,head[maxn],cnt;
long long dis[maxn],dq[maxn],ans;
bool used[maxn];
queue <int> q;

struct node{
    int to,nxt;
    long long w;
}edge[maxn*];

void add(int x,int y,long long z)
{
    cnt++;
    edge[cnt].to=y;
    edge[cnt].nxt=head[x];
    edge[cnt].w=z;
    head[x]=cnt;
}

bool spfa(int s)
{
    for(int i=;i<=n;i++)
    {
        dis[i]=inf;
        used[i]=;
    }
    dis[]=dis[s]=; 
    q.push(s);
    used[s]=;
    while(!q.empty())
    {
        int x;
        x=q.front(); q.pop();
        used[x]=;
        for(int i=head[x];i;i=edge[i].nxt)
        {
            int y=edge[i].to;
            if(dis[x]+edge[i].w<dis[y])
            {
                dis[y]=dis[x]+edge[i].w;
                if(!used[y])
                {
                    used[y]=;
                    q.push(y);
                }
            }
        }
    }
    for(int i=;i<=n;i++)
    {
        if(dis[i]==inf) return false;
    }
    return true;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        cnt=,ans=;
        memset(head,,sizeof head); memset(dq,,sizeof dq);
        dis[]=;
        for(int i=;i<=n;i++)
        {
            scanf("%d",&dq[i]);
        }
        for(int i=;i<=m;i++)
        {
            int x,y;
            long long z;
            scanf("%d%d%lld",&x,&y,&z);
            add(x,y,z); add(y,x,z);
        }
        if(spfa())
        {
            for(int i=;i<=n;i++)
            {
                ans+=dq[i]*dis[i];
            }
            printf("%lld\n",ans);
        }
        else printf("No Answer\n");
    }
    return ;
}