求最多能经过的点,那其实就是从起点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; }