最短路
题意：给n个点从1到n标号，下面一行是每个点的权，另外给出m条边，下面是每条边的信息，两个端点+权值，边是无向边。你的任务是选出一些边，使这个图变成一棵树。这棵树的花费是这样算的，1号固定为树根，树中每个双亲节点下面的边都有个单价（即边权），然后单价乘上这条边的下面所有的子孙后代的点权和（看sample2，只要除掉边 1 5 9 按照这个方法就能算出1210）
分析：把sample2用式子列一下就能发现，每个点的权都要乘上好几条边的权，是哪几条边呢，就是这个点回到点1的路径上的那些边
所以最后的树的花费可以写成 res = sum{ (点权) * (该点回到点1的路径的边权和) } ，这些点是2到n，1是不用算的
所以决定这条式子大小的，只有 (该点回到点1的路径的边权和) ， 只要能让它最小即可。 令到每个点回到点1的路径边权和最小是什么？就是最短路啊！
所以从点1运行一次最短路，就可以知道1到每个点的最短路（也就是每个点到点1的最短路，因为无向图）
但是要注意一个坑，没看清楚题意，超时了很多次，就是点数可能为0（太坑了），点数为0运行不了最短路一直卡在里面，所以特判一下，输出0，如果点数1同样也是0的，因为整个树不会有边
另外注意网上的各种说法
1.有人说dij过不了，是能过的
2.有人说dij要手写heap才能过，直接用STL的优先队列也是能过的
3.spfa能过
4.这题没试过用vector建图，建议不要，可能真的是过不了，毕竟点很多
这个是dij+stl优先队列
#include <cstdio> #include <cstring> #include <utility> #include <queue> #include <vector> using namespace std; const int N = 50010; const __int64 INF = 10000000000; int n,tot; __int64 d[N]; int val[N]; int head[N]; bool done[N]; struct edge { int u,v,w,next; }e[2*N]; typedef pair<__int64,int>plli; priority_queue<plli , vector<plli> , greater<plli> > q; void add(int u ,int v , int w , int k) { e[k].u = u; e[k].v = v; e[k].w = w; e[k].next = head[u]; head[u] = k++; u = u^v; v = u^v; u = u^v; e[k].u = u; e[k].v = v; e[k].w = w; e[k].next = head[u]; head[u] = k++; } __int64 Dij() { int count = 0; __int64 res = 0; d[1] = 0; q.push(make_pair(d[1] , 1)); while(!q.empty()) { int u,v,w; plli x = q.top(); q.pop(); u = x.second; if(done[u]) continue; done[u] = true; count++; res += d[u] * val[u]; for(int k=head[u]; k!=-1; k=e[k].next) { v = e[k].v; w = e[k].w; if(d[u] + w < d[v]) { d[v] = d[u] + w; q.push(make_pair(d[v] , v)); } } } if(count < n) return -1; else return res; //熟悉heap+dij的本质，可以在dij过程中就统计出所有点的最短路和并乘上他们的权 //不需要dij结束后去扫描一次所有点来计算，并且可以在dij过程判断是否能构成一棵树 } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&tot); for(int i=1; i<=n; i++) scanf("%d",&val[i]); while(!q.empty()) q.pop(); for(int i=1; i<=n; i++) { head[i] = -1; d[i] = INF; done[i] = false; } for(int i=1; i<=2*tot; i+=2) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w,i); } if(n == 0 || n == 1) //注意这个坑，会超时，出现n=0点的时候 { printf("0\n"); continue; } __int64 res = Dij(); if(res != -1) printf("%I64d\n",res); else printf("No Answer\n"); } return 0; }
2.dij+手写heap，复习嘛，复习嘛，又很久没手写过heap了，手写的只比STL快了20ms
#include <cstdio> #include <cstring> #include <utility> using namespace std; const int N = 50010; const __int64 INF = 10000000000; int n,tot; __int64 d[N]; __int64 val[N]; int head[N]; bool done[N]; struct edge { int u,v,next; __int64 w; }e[2*N]; typedef pair<__int64,int>plli; plli heap[2*N]; int num; void add(int u ,int v , __int64 w , int k) { e[k].u = u; e[k].v = v; e[k].w = w; e[k].next = head[u]; head[u] = k++; u = u^v; v = u^v; u = u^v; e[k].u = u; e[k].v = v; e[k].w = w; e[k].next = head[u]; head[u] = k++; } int cmp(plli x , plli y) {//x的最短路径估计值小，则返回1，否则返回0 return x.first < y.first; } plli top() { return heap[1]; } void push(plli x) { int par,son; plli temp = x; heap[++num] = x; for(son = num , par=son/2; son > 1; son=par , par = son/2) { if(cmp(temp , heap[par])) //儿子更小，向上移动 heap[son] = heap[par]; //父亲滑下来覆盖儿子 else break; //终于儿子已经比父亲大了，那么不用再比较了 } heap[son] = temp; } void pop() { int son,par; plli temp; heap[1] = heap[num--]; temp = heap[1]; for(par=1 , son=par*2; son<=num; par=son , son=par*2) { if(son < num && cmp(heap[son+1] , heap[son])) son++; if(cmp(temp , heap[son])) break; heap[par] = heap[son]; } heap[par] = temp; } __int64 Dij() { int count = 0; __int64 res = 0; d[1] = 0; push(make_pair(d[1] , 1)); while(num>0) { int u,v; __int64 w; plli x = top(); pop(); u = x.second; if(done[u]) continue; done[u] = true; count++; res += d[u] * val[u]; for(int k=head[u]; k!=-1; k=e[k].next) { v = e[k].v; w = e[k].w; if(d[u] + w < d[v]) { d[v] = d[u] + w; push(make_pair(d[v] , v)); } } } if(count < n) return -1; else return res; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&tot); for(int i=1; i<=n; i++) scanf("%I64d",&val[i]); if(n == 0 || n == 1) { printf("0\n"); continue; } num = 0; for(int i=1; i<=n; i++) { head[i] = -1; d[i] = INF; done[i] = false; } for(int i=1; i<=2*tot; i+=2) { int u,v; __int64 w; scanf("%d%d%I64d",&u,&v,&w); add(u,v,w,i); } __int64 res = Dij(); if(res != -1) printf("%I64d\n",res); else printf("No Answer\n"); } return 0; }