题目

我的记录

代码（个人码分可能不好，请见谅）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){int x=0,ff=1;char ch = getchar();while(ch<'0'||ch>'9'){if(ch=='-')ff = -1;ch = getchar();}while(ch>='0'&&ch<='9')x = x*10+ch-'0',ch = getchar();return x*ff;}
struct A{
	int x;
	long long len;
};
bool operator<(A x,A y){
	return x.len>y.len;
}
priority_queue<A>q;
vector<A> v[310000];
int n,m,w;
long long ans=0,sum=0;
int a[310000],vv[310000];
long long f[310000];
void djs(int yd){
	memset(f,63,sizeof(f));
	f[yd] = 0;
	q.push({yd,0});
	while(!q.empty()){
		A k = q.top();
		q.pop();
		int x = k.x;
		if(vv[x])continue;
		vv[x] = 1;
		ans++;
		for(int i=0;i<(int)v[x].size();i++){
			int y = v[x][i].x;
			if(f[y]>f[x]+v[x][i].len&&a[x]>=a[y]){
				f[y] = f[x]+v[x][i].len;
				q.push({y,f[y]});
			}
		}
	}
}
struct B{
    int x,y,len;
}c[310000];
B d[310000];
int fa[310000];
bool cmp(B x,B y){
    return x.len<y.len;
}
int find(int x){
    if(fa[x]==x) return x;
    else return fa[x] = find(fa[x]);
}
void jr(int x,int y,int z){
	int p = find(x),q = find(y);
	if(q!=p) fa[p] = q,sum+=z;
}
signed main(){
	n = read();m = read();
	for(int i=1;i<=n;i++)a[i] = read();
	for(int i=1;i<=m;i++){
		int x = read(),y = read(),z = read();
		v[x].push_back({y,z});
		v[y].push_back({x,z});
		c[i].x = x;c[i].y = y;c[i].len = z;
	}
	djs(1);
	for(int i=1;i<=m;i++) if(vv[c[i].x]&&vv[c[i].y]){
		d[++w].x = c[i].x;
		d[w].y = c[i].y;
		d[w].len = c[i].len;
	}
	sort(d+1,d+1+w,cmp);
	for(int i=1;i<=n;i++)fa[i] = i;
	for(int i=1;i<=w;i++)jr(d[i].x,d[i].y,d[i].len);
	cout<<ans<<" "<<sum;
	return 0;
}