RT,后面两个点都过了,前面三个反而没过,求各位帮忙看看。
#include<bits/stdc++.h>
#define MAXN 100010
#define MAXM 1000010
using namespace std;
typedef long long ll;
struct edge{ int pre, to; ll w; };
struct node{ int high; ll dis; int id; };
bool operator < (node a, node b){
if(a.high == b.high) return a.dis > b.dis;
return a.high < b.high;
}
bool operator > (node a, node b){
if(a.high == b.high) return a.dis < b.dis;
return a.high > b.high;
}
edge e[MAXM];
int n, m, cnt; ll tot, ans;
int h[MAXN], head[MAXN];
ll dis[MAXN];
bool vis[MAXN];
void add_edge(int u, int v, int w){
e[++cnt].pre = head[u];
e[cnt].to = v; e[cnt].w = w;
head[u] = cnt;
}
void prim(int st){
memset(dis, 0x3f, sizeof(dis));
priority_queue<node> q;
dis[st] = 0; q.push((node){h[st], 0, st});
while(!q.empty()){
int now = q.top().id; q.pop();
if(vis[now]) continue;
vis[now] = true;
tot++; ans += dis[now];
for(int i = head[now]; i; i = e[i].pre){
if(vis[e[i].to]) continue;
if(dis[e[i].to] > e[i].w){
dis[e[i].to] = e[i].w;
q.push((node){h[e[i].to], dis[e[i].to], e[i].to});
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) scanf("%d",&h[i]);
for(int i = 1; i <= m; i++){
int u, v; ll w; scanf("%d%d%lld",&u,&v,&w);
if(h[u] >= h[v]) add_edge(u, v, w);
if(h[v] >= h[u]) add_edge(v, u, w);
}
prim(1);
printf("%lld %lld\n",tot,ans);
return 0;
}