题目

分析

题目乍看一下像最短路径的求解。但是从复杂度上面分析应该不是这样。题目关键点在于“路程花费是最贵的那一段” 和 “最少花费在区间内”。

合起来就是两点所有路程中最便宜的最贵段，要在区间内：如果按权值从小到大遍历边，能合并连通块的边就是某两点所有路程中最便宜的最贵段（后续再有边一定更贵，前面虽然便宜，但没有形成一个完整的路径）。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+10;
const int M = 2e5+10;
int n, m, l, r;
int p[N], sz[N];
struct edge{int a, b, c;bool operator < (edge& y){return c < y.c;}
}e[M];
int find(int x)
{if(p[x] != x) p[x] = find(p[x]);return p[x];
}
int main()
{cin >> n >> m >> l >> r;for(int i = 1; i <= n; i++)p[i] = i, sz[i] = 1;for(int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;e[i] = {a, b, c};}sort(e+1, e+m+1);ll ans = 0;for(int i = 1; i <= m && e[i].c <= r; i++){int pa = find(e[i].a), pb = find(e[i].b);if(pa != pb){if(e[i].c >= l) ans += (ll)sz[pa] * sz[pb];p[pa] = pb;sz[pb] += sz[pa];}}cout << ans;
}