poj3013 Big Christmas Tree --- 最短路

我都不好意思在标題上寫這是最短路

這題挺有意思，關鍵在于把題目所求的量轉換為最短路問題。

題意：

給一個無向圖，每個結點有權值p[i]，每條邊有權值w[i]

求使這顆樹所有頂點與根節點1聯通的最小花費，

最小花費=∑w[i]×∑p[i]

第一個∑是所有邊，第二個∑是該邊下所有結點的權值和

思路：

通過推導可以發現，對于每個結點，它被算入的花費為 p[i]*d[i]，

d[i]為該結點到根結點的距離。

于是豁然開朗了吧。。水題一道

唯一的坑點是要int64，而且inf要足夠大

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
const ll inf=1ll<<60;//坑死！這題inf必須足夠大
#define N 50010
#define M 100010

struct node
{
    int v,next;
    ll w;
}e[M];
int vis[N],n,m,head[N],h;
ll d[N],p[N];

void addedge(int a,int b,ll c)
{
    e[h].v=b;
    e[h].w=c;
    e[h].next=head[a];
    head[a]=h++;
}

int spfa(int st)
{
    memset(vis,0,sizeof vis);
    for(int i=0;i<=n;i++)
        d[i]=inf;
    d[st]=0;
    vis[st]=1;
    queue<int> q;
    q.push(st);
    int x,i,v;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        vis[x]=0;
        for(i=head[x];i!=-1;i=e[i].next)
        {
            v=e[i].v;
            if(d[v]>d[x]+e[i].w)
            {
                d[v]=d[x]+e[i].w;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}

void init()
{
    memset(head,-1,sizeof head);
    h=0;
}

int main()
{
    int t,a,b,i;
    ll ans,c;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            cin>>p[i];
        while(m--)
        {
            scanf("%d%d",&a,&b);
            cin>>c;
            addedge(a,b,c);
            addedge(b,a,c);
        }
        spfa(1);
        ans=0;
        int flag=1;
        for(i=2;i<=n;i++)
        {
            if(d[i]==inf)
            {
                flag=0;
                break;
            }
            ans+=(d[i]*p[i]);
        }
        if(!flag)  printf("No Answer\n");
        else cout<<ans<<endl;
    }
    return 0;
}