传送门

分析

本题的要点在于i到j有通路必须所有我们可以根据给出的建图。
那么第一个问题就是求从1出发，最多可以经过多少个点，这个问题用BFS/DFS统计下点的个数即可。
主要问题在于第二个问题，因为题目说不考虑时间胶囊的消耗，而且可以连续食用，所以最后走出来的形状一定是树的样子。但是由于路线方向是根据的高度所决定的，只能从高处到低处，所以并不是最小生成树。
但是本题可以理解为一个最小生成树的变型问题，在本题中若从点u到点v，必须满足如下的要求：

1. u和v都和起点连通
2. 

那我们可以根据算法的思想，定义以下的排序原则：

• 若，则按照来排序
• 否则按照高度排序

这样相当于我们在一层一层扩展，先把最高层的点加入最小树形图然后次高层依次类推，这样所有的边就是按照从高的低的方向走的了。

Tags

• 最小生成树
• 树论

参考代码

//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}
int n, m;
ll h[maxn], fa[maxn];
vector<int> e[maxn];

struct Edge {
    int u, v;
    ll w;
    Edge(const int &u = 0, const int &v = 0, const ll&w = 0) :
        u(u), v(v), w(w) { }
    bool operator<(const Edge & E) const {
        if (h[v] == h[E.v]) return w < E.w;
        return h[v] > h[E.v];
    }
};

vector<Edge> a;
void init() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int vis[maxn];
ll bfs(int x) {
    ll ans = 0;
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        ans++;
        for (auto &x : e[u]) {
            q.push(x);
        }
    }
    return ans;
}

ll kruskal() {
    ll ans = 0;
    sort(a.begin(), a.end());
    for (auto & x : a) {
        int u = x.u, v = x.v;
        ll w = x.w;
        if (!vis[u] || !vis[v]) continue;
        int fx = find(u);
        int fy = find(v);
        if (fx != fy) {
            fa[fx] = fy;
            ans += w;
        }
    }
    return ans;
}

int main(void) {
    FAST_IO;

    cin >> n >> m;
    init();
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (h[v] >= h[u]) {
            e[v].push_back(u);
            a.emplace_back(v, u, w);
        }
        if (h[u] >= h[v]) {
            e[u].push_back(v);
            a.emplace_back(u, v, w);

        }
    }
    ll ans1 = bfs(1);
    ll ans2 = kruskal();
    cout << ans1 << " " << ans2 << endl;

    return 0;
}