题意:每个顶点有一个权值,求构造一个图,使得 ∑(每个点的权值)X(到1结点的距离) 最小
方法:dijkstra+heap
昨晚写了一个,不知道为什么TLE,怎么改都TLE。今天重写一遍AC了
#include<cstdio> #include<queue> #include<cstring> using namespace std; #define MAXN 50005 #define MAXM 100005 #define INF 10000000000 int 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<dist; } }; bool done[MAXN]; long long dis[MAXN]; int n,m; inline void dijkstra() { memset(done,0,sizeof(done)); priority_queue<Node> 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<m;i++) { scanf("%d%d%d",&tmpf,&tmpt,&tmpd); addedge(tmpf,tmpt,tmpd); } dijkstra(); long long ans=0; for(int i=1;i<=n;i++) { if(dis[i]==INF) { ans=-1; break; } ans+=dis[i]*val[i]; } if(ans==-1) printf("No Answer\n"); else printf("%lld\n",ans); } return 0; }