题目描述
a180285非常喜欢滑雪。他来到一座雪山，这里分布着 M 条供滑行的轨道和 N 个轨道之间的交点（同时也是景点），而且每个景点都有一编号 i ( 1≤i≤N )和一高度 Hi。a180285能从景点 i 滑到景点 j 当且仅当存在一条 i 和 j 之间的边，且 i 的高度不小于 j 。 与其他滑雪爱好者不同，a180285喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。于是a180285拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点（不用移动也不被认为是a180285 滑行的距离）。请注意，这种神奇的药物是可以连续食用的，即能够回到较长时间之前到过的景点（比如上上个经过的景点和上上上个经过的景点）。 现在，a180285站在 111 号景点望着山下的目标，心潮澎湃。他十分想知道在不考虑时间胶囊消耗的情况下，以最短滑行距离滑到尽量多的景点的方案（即满足经过景点数最大的前提下使得滑行总距离最小）。你能帮他求出最短距离和景点数吗？
输入输出格式
输入格式：
输入的第一行是两个整数 N,M 。
接下来 1行有 N个整数 Hi ，分别表示每个景点的高度。
接下来 M行，表示各个景点之间轨道分布的情况。每行 3 个整数， Ui,Vi,Ki。表示编号为 Ui的景点和编号为 Vi的景点之间有一条长度为 Ki 的轨道。
输出格式：
输出一行，表示a180285最多能到达多少个景点，以及此时最短的滑行距离总和。
输入输出样例
3 3
3 2 1
1 2 1
2 3 1
1 3 10
3 2
说明
【数据范围】
对于 30% 的数据，保证 1≤N≤2000
对于 100% 的数据，保证 1≤N≤105
对于所有的数据，保证 1≤M≤106 , 1≤Hi≤109， 1≤Ki≤109 。
Solution：
本题ZYYS（吐槽：每次复制题面，都要炸markdown格式，好不爽啊，懒人不想改～）。
老鱼讲朱刘算法时提到这题，结果朱刘算法是本题暴力分？
正解：bfs+kruscal
我们先从1广搜，就能处理出最多能到达的点的个数，在bfs的同时，建一张新图，因为有向，所以要在新图中求最小树形图。
由于有高度限制（边有向），克鲁斯卡尔的排序过程就不能简单的按边权排序了，否则就会出现高度低的点指向高度高的点的情况，所以我们应该先让高度高的连向高度低的点，因为新图满足$H[u]\geq H[v]$，于是按所到点的高度为第一关键字从大到小排序，边权为第二关键字从小到大排序，再做kruscal就是正确的了。
代码：
/*Code by 520 -- 8.21*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=;
int n,m,to[N],net[N],w[N],h[N],cnt,H[N];
int fa[N],tot;
struct node{
int u,v,w;
bool operator < (const node &a)const{return H[v]==H[a.v]?w<a.w:H[v]>H[a.v];}
}e[N];
bool vis[N]; int gi(){
int a=;char x=getchar();
while(x<''||x>'')x=getchar();
while(x>=''&&x<='')a=(a<<)+(a<<)+(x^),x=getchar();
return a;
} int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} il void add(int u,int v,int c){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt,w[cnt]=c;} void bfs(){
queue<int>q;
q.push(),vis[]=;
while(!q.empty()){
int u=q.front();q.pop();
for(RE int i=h[u];i;i=net[i]){
e[++cnt].u=u,e[cnt].v=to[i],e[cnt].w=w[i];
if(!vis[to[i]]) vis[to[i]]=,tot++,q.push(to[i]);
}
}
} il void init(){
n=gi(),m=gi();
For(i,,n) fa[i]=i,H[i]=gi();
int u,v,c;
For(i,,m) {
u=gi(),v=gi(),c=gi();
if(H[u]>=H[v]) add(u,v,c);
if(H[u]<=H[v]) add(v,u,c);
}
cnt=,bfs();
sort(e+,e+cnt+);
ll ans=;
For(i,,cnt) {
int u=find(e[i].u),v=find(e[i].v);
if(u!=v) fa[u]=v,ans+=e[i].w;
}
cout<<tot+<<' '<<ans;
} int main(){
init();
return ;
}