【CJOJ P2226】[省常中2011S4] 圣诞节

Description

圣诞节到了，FireDancer准备做一棵大圣诞树。下图为圣诞树的一个简单结构。

这棵树被表示成一组被编号的结点和一些边的集合。结点从1到n编号。树的根永远是1。每个结点都有一个自身特有的数值，称为它的重。各个结点的重可能不同。对于一棵做完的树来说，每条边都有一个价值，若设这条边e连接结点i和结点j，且i为j的父结点(根是最老的祖先)，则该边的价值为(j的所有子孙及它自己的重之和)*（e的单位价值ce）。

现在FireDancer想造一棵树，使得树上所有边的总价值最小，并且所有的点都在树上，因为FireDancer喜欢大树。

Input

第一行两个整数n和m（0<=n,m<=50000），表示结点总数和可供选择的边数。

下面一行有n个整数，依次表示每个结点的重。

下面m行，每行有3个正整数a,b,c，表示结点a和结点b之间有一个单位价值为c的边可供你造树时选择。

输入中的所有数都小于2^16。

Output

若无解，输出“No Answer”，否则一个整数表示造树的最小价值。

Sample Input

[样例输入1]

2 1

1 1

1 2 15

[样例输入2]

7 7

200 10 20 30 40 50 60

1 2 1

2 3 3

2 4 2

3 5 4

3 7 2

3 6 3

1 5 9

Sample Output

[样例输出1]

15

[样例输出2]

1210

题解

观察发现得到的最大圣诞树所有边的价值总和最小恰好等于根节点到其余各节点的最短路径乘以每个节点的重之和。最后边的价值总和中对于圣诞树中某个节点它的重会乘以什么东西呢？很显然恰好乘的是根节点到该节点的最短路径。因此就是求出每个节点到根节点的最短距离，问题迎刃而解。

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

const int maxsize=50000;

const long long inf=2147483647;

const int maxE=100;

class edge

{

    public:

    int k;

    short int e[maxE];

    short int w[maxE];

    edge()

    {

        k=0;

    }

};

int n,m;

short int node[maxsize]={0};

bool ok[maxsize]={0};

int dist[maxsize]={0};

edge E[25000];

long long sum;

int main()

{

    int i,j,k;

    int x,y;

    int Node;

        //input

    cin>>n>>m;

    for (i=1;i<=n;i++)

    cin>>node[i];

    for (i=1;i<=m;i++)

    {

        cin>>x>>y;

        E[x].k++;

        E[x].e[E[x].k]=y;

        cin>>E[x].w[E[x].k];

        E[y].k++;

        E[y].e[E[y].k]=x;

        E[y].w[E[y].k]=E[x].w[E[x].k];

    }//用结构体储存内容

    for (i=1;i<=n;i++)

        dist[i]=inf;//dis值赋初值

    dist[1]=0;

    for (i=1;i<=n;i++)

    {

        k=inf;

        for (j=1;j<=n;j++)

        {

            if ((dist[j]<k)&&(ok[j]==0))

            {

                k=dist[j];

                Node=j;

            }

        }

        ok[Node]=1;

        for (j=1;j<=E[Node].k;j++)

        if (ok[E[Node].e[j]]==0)

        {

            x=E[Node].e[j];

            if (dist[Node]+E[Node].w[j]<dist[x])

            {

                dist[x]=dist[Node]+E[Node].w[j];

            }

        }

    }//迪杰斯特拉算法

    sum=0;

    for (i=1;i<=n;i++)

        sum=sum+dist[i]*node[i];

    cout<<sum<<endl;//计算和输出

    return 0;

}//借鉴萝卜代码，自己的找不到了。感谢萝卜songyuchen0001

巴特西