求最多能经过的点,那其实就是从起点1开始看他后面能到多少个点。bfs或者dfs一下 O(n)复杂度即可处理出来结果
对于第二个最少的距离,因为用胶囊回去的话,一条路只算一次长度,有点像最小生成树,但是因为题中的边是有方向的,不能够直接最小生成树,所以对高度降序,高度一样路径长度升序。
因为高度降序,保证前面的点一定可以到达后面的点,高度一样贪心取最小值。
为什么直接最小生成树不行呢
如下图
图片说明
圆圈内的数字为点的高度 9为根节点
如果直接最小生成树肯定选择边权为10 和边权为1的边,但是容易发现根节点9是无法直接到7的 这样的做法是错误的
所以按照高度排序后,先选择边权为10的然后选择边权为12的才是正确的

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Edge
{
    ll from,to, v, ne;
} e[1 << 21];
ll h[1 << 21], tot;
ll a[1 << 21];
bool vis[1 << 21];
void add_edge(ll a, ll b, ll c)
{
    e[tot].from=a,e[tot].to = b, e[tot].v = c;
    e[tot].ne = h[a], h[a] = tot++;
}
ll f[1 << 21];
ll find(ll x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
int main()
{
    ios::sync_with_stdio(0);
    ll n, m;
    cin >> n >> m;
    ll cnt = 0;
    for (ll i = 1; i <= n; i++)
        cin >> a[i], h[i] = -1, f[i] = i;
    for (ll i = 1; i <= m; i++)
    {
        ll x, y, d;
        cin >> x >> y >> d;
        if (a[x] >= a[y])
            add_edge(x, y, d);
        if (a[y] >= a[x])
            add_edge(y, x, d);
    }
    queue<ll> que;
    ll ans = 0;
    que.push(1);
    while (!que.empty())
    {
        ll now = que.front();
        que.pop();
        if(vis[now]) continue;
        vis[now]=1;
        ans++;
        for (ll i = h[now]; ~i; i = e[i].ne) que.push(e[i].to);
    }
    cout << ans << " ";
    ll sum = 0;
    sort(e , e + tot, [](Edge x, Edge y) {
        if(a[x.to] == a[y.to]) return x.v<y.v;
        return a[x.to]>a[y.to];
    });
    ll num = 0;
    for (ll i = 0; i < tot; i++)
    {
        if (vis[e[i].from] && vis[e[i].to])
        {

            ll fx = find(e[i].from), fy = find(e[i].to);
            if (fx != fy)
            {
                f[fx] = fy;
                sum += e[i].v;
                num++;
                if (num == ans - 1)
                    break;
            }
        }
    }
    cout << sum;
    return 0;
}