题意：每个顶点有一个权值，求构造一个图，使得 ∑(每个点的权值)X(到1结点的距离) 最小

方法：dijkstra+heap

昨晚写了一个，不知道为什么TLE，怎么改都TLE。今天重写一遍AC了

#include
     
      #include
      
       #include
       
        using namespace std;#define MAXN 50005#define MAXM 100005#define INF 10000000000int edge_cnt;int val[MAXN];int first[MAXN];struct edge_node{	int to,weight,next;}edges[MAXM];inline void addedge(int f,int t,int dis){	++edge_cnt;	edges[edge_cnt].to=f;	edges[edge_cnt].weight=dis;	edges[edge_cnt].next=first[t];	first[t]=edge_cnt;	++edge_cnt;	edges[edge_cnt].to=t;	edges[edge_cnt].weight=dis;	edges[edge_cnt].next=first[f];	first[f]=edge_cnt;}struct Node{	int point,dist;	bool operator<(const Node x) const	{		return x.dist
        
          Que;	Node tmp,inq;	tmp.point=1;tmp.dist=0;	for(int i=0;i<=n;i++)		dis[i]=INF;	dis[1]=0;	Que.push(tmp);	int u,v,e;	while(!Que.empty())	{		tmp=Que.top();Que.pop();		u=tmp.point;		if(done[u])			continue;		done[u]=true;		for(e=first[u];e;e=edges[e].next)		{			v=edges[e].to;			if(!done[v]&&dis[v]>dis[u]+edges[e].weight)			{				dis[v]=dis[u]+edges[e].weight;				inq.dist=dis[v];				inq.point=v;				Que.push(inq);			}		}	}}int main(){	int T;	scanf("%d",&T);	while(T--)	{		edge_cnt=0;		scanf("%d%d",&n,&m);		for(int i=1;i<=n;i++)			scanf("%d",&val[i]);		int tmpf,tmpt,tmpd;		memset(first,0,sizeof(first));		for(int i=0;i