~~为什么不发题解~~
by 绝顶我为峰 @ 2018-07-28 19:55:09
感谢，我正好没AC
by 小粉兔 @ 2018-07-28 19:59:10
太强啦！您这篇文章可以作为国集论文了！
by 冈崎梦美 @ 2018-07-28 20:08:13
~~笑点在哪~~
by lolte @ 2018-07-28 20:12:17
# 简单
by UKE自动稽 @ 2018-07-28 20:16:16
tql
by moye到碗里来 @ 2018-07-28 20:17:42
!!!
by Sya_Resory @ 2018-07-28 20:19:19
@[Dream_Chaser](/space/show?uid=114082) @[moye到碗里来](/space/show?uid=52576) @[_UKE自动机_](/space/show?uid=71371) @[lolte](/space/show?uid=78752) @[LGW2016B02](/space/show?uid=41953) @小粉兔 @蒟蒻烟雨平生
最新优化代码：
```
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5001;
const int MAXM = 200001;
struct Line {
int p;
int v;
int next;
}line[MAXM*2];
struct Node{
int dist;
int heapindex;
}node[MAXN];
int hline[MAXN];
int heap[MAXN];
int n, m, z, x, y;
void add(int d, int x, int y, int z) {
line[d].p = y;
line[d].v = z;
line[d].next = hline[x];
hline[x] = d;
}
int find() {
int p = 0;
for(int i = 1;i <= n; i++) {
if (!node[i].heapindex) {
if ((p == 0) || (node[i].dist < node[p].dist)) {
p = i;
}
}
}
return p;
}
void swap(int i, int j){
int k = heap[i];
heap[i] = heap[j];
heap[j] = k;
node[heap[i]].heapindex = i;
node[heap[j]].heapindex = j;
}
void down(int i,int hn){
int j = i * 2;
while(j<=hn){
if ((j + 1)&&(node[heap[j + 1]].dist < node[heap[j]].dist)){
j++;
}
if(node[heap[i]].dist > node[heap[j]].dist) {
swap(i, j);
i = j;
j = i * 2;
}else{
break;
}
}
}
void up1(int i){
while(i&&node[heap[i]].dist < node[heap[i / 2]].dist) {
swap(i, i / 2);
i /= 2;
}
}
void up(int now) {
int i = hline[now];
while(i){
int p = line[i].p;
if (node[p].heapindex) {
if (line[i].v < node[p].dist) {
node[p].dist = line[i].v;
up1(node[p].heapindex);
}
}
i = line[i].next;
}
}
int main() {
cin>> n>> m;
for(int i = 1;i <= m; i++) {
cin>> x>> y>> z;
add (i * 2 - 1, x, y, z);
add (i * 2, y, x, z);
}
for(int i = 1;i <= n; i++) {
node[i].dist = (1 << 31) - 1;
node[i].heapindex = i;
heap[i] = i;
}
node[1].dist = 0;
int ans = 0;
for(int i = n;i >= 1; i--) {
int now = heap[1];
ans += node[now].dist;
node[now].heapindex = 0;
heap[1] = heap[i];
down(1,i-1);
up(now);
}
cout<<ans;
return 0;
}
```
by 御·Dragon @ 2018-07-28 20:32:44
@[封禁用户名f8617dda](/space/show?uid=37682) 一下@那么多人很烦的！
by UKE自动稽 @ 2018-07-28 20:33:25
@[_UKE自动机_](/space/show?uid=71371) 还好滑稽
by 御·Dragon @ 2018-07-28 20:34:14