学步园

题意：要建一棵圣诞树，使得总的花费最小。具体规则是：圣诞树是一颗无向树形图，其中，编号为1的节点为根节点，原始图中每条边具有边权（unit）：材料的单位价值，每个点也有一个权(weight)：点的重量。总的花费则是生成树中所有点的花费之和。
而每个点的花费为 根结点到该点的距离（边权unit）* 该点的重量。

思路：求出各点的最短路径 再与点的重量相乘之和； 注意两点我觉得，inf 要定义足够大，10个9吧，还有，用memset
初始化会严重超时，不用竟然才600多MS 。。。。这个我无语了。。。。

#include <stdio.h>
#include <string.h>
#define VM 50005
#define EM 100005
#define inf 9999999999
int head[VM],ep;
int weigt[VM];
struct dege
{
    int
v,w,next;
} e[EM];
void addedge(int cu,int cv,int cw)
{
    ep ++;
    e[ep].v =
cv;
    e[ep].w =
cw;
    e[ep].next =
head[cu];
    head[cu] =
ep;
}

__int64 spfa (int n)
{
    int
vis[VM],queue[VM],cnt[VM];
    __int64
dis[VM];
    //memset
(vis,0,sizeof(vis));
    //memset
(cnt,0,sizeof(cnt));
    // memset
(dis,0x3f,sizeof(dis));
    for (int i =
1; i <= n; i ++)
    {
       
cnt[i] = 0;
       
vis[i] = 0;
       
dis[i] = inf;
    }
    dis[1] =
0;
    int front =
-1,rear = 0;
   
queue[rear++] = 1;
    vis[1] =
1;
    cnt[1] =
1;
    while (front
!= rear)
    {
       
front = (front+1)%(n+1);
       
int u = queue[front];
       
vis[u] = 0;
       
for (int i = head[u]; i != -1; i = e[i].next)
       
{
           
int v = e[i].v;
           
if (dis[v] > dis[u] + e[i].w)
           
{
               
dis[v] = dis[u] + e[i].w;
               
if (!vis[v])
               
{
                   
vis[v] = 1;
                   
queue[rear] = v;