Solution

这题在洛谷上是紫题, 但是好像没有想象中那么难
很容易看出这题是要求从点 开始扩展的最小生成树
因为有一个高度的限制, 不能直接求
如果用 的话好像不知道怎么下手
这个时候想到了用堆优化的
在优先队列里我们多加一个条件
即先往高度大的地方走, 不行再往当前连通块的最近点走即可
注意题目没给数据范围, 数组要开到

Code

/*
  autor: Kurisu
  2020年4月30日16:48:49
*/
#include<bits/stdc++.h>
using namespace std;

const long long inf = 1e18;
const int N = 1e6 + 5;
const double eps = 1e-10;
const int mod = 1e9 + 7;
typedef long long ll;
struct Edge {
  int v, nextz;
  ll cost;
}edge[N << 1];
int tot, head[N];
void addedge(int u, int v, ll w) {
  edge[tot].v = v;
  edge[tot].cost = w;
  edge[tot].nextz = head[u];
  head[u] = tot++;
}
struct qnode {
  int v, h;
  ll dis;
  qnode(int _v = 0,int  _h = 0, ll _dis = 0): v(_v), h(_h), dis(_dis){}
  bool operator < (const qnode &s) const {
    return h == s.h ? dis > s.dis : h < s.h;
  }
};
int val[N], cnt, n, m;;
bool vis[N];
ll dist[N], ans;
void prim() {
  for(int i = 1; i <= n; i++) dist[i] = inf;
  priority_queue<qnode> q;
  q.push(qnode(1, val[1], 0));
  dist[1] = 0;
  while(!q.empty()) {
    qnode tmp = q.top();
    q.pop();
    int u = tmp.v;
    if(vis[u]) continue;
    vis[u] = 1;
    cnt++, ans += dist[u];
    for(int i = head[u]; ~i; i = edge[i].nextz) {
      int v = edge[i].v;
      ll cost = edge[i].cost;
      //cout << v << ' ' << cost << "\n";
      if(!vis[v] && dist[v] > cost) {
        dist[v] = cost;
        q.push(qnode(v, val[v], dist[v]));
      }
    }
  }
}
int main() {
  memset(head, -1, sizeof(head));
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> val[i];
  while(m--) {
    int u, v;
    ll w;
    cin >> u >> v >> w;
    if(val[u] >= val[v]) addedge(u, v, w);
    if(val[v] >= val[u]) addedge(v, u, w);
  }
  prim();
  cout << cnt << ' ' << ans << "\n";
  return 0;
}