该题因为是可以在一条路径上来回跑 所以只需要判断跑步中的最大米数是否大于起点到每条边的两个点中的最短路的最小值乘2 也就是说 这两个点任何一个点到起点的最小距离乘2 小于跑步中的最大米数 这条边就可以被选取 答案加1
所以只需要用dijkstra跑出来到所有点的最短距离再进行判断答案就可以了
#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int M = 100010;
const int INF = 0x3f3f3f3f;
typedef pair<int, int>PII;
int cnt = 0;
// 存边的两点
PII edge[M];
// 存点能连接到的点
vector<PII> head[M];
int dis[M];
bool vis[M];
void add_edge(int u, int v, int w) {edge[cnt++] = { u, v };head[u].push_back({ v, w });head[v].push_back({ u, w });
}
void dij() {priority_queue<PII, vector<PII>, greater<PII> > que;// 优先根据第一个元素递增排序 第一个元素选择起点到第二个元素的长度que.push({ 0, 0 });int v, w;while (!que.empty()) {// w 表示起点到下一个候选点的距离 v表示下一个候选点w = que.top().first; v = que.top().second; que.pop();if (vis[v]) continue; vis[v] = 1;for (auto i : head[v]) {if (dis[i.first] > dis[v] + i.second) {dis[i.first] = dis[v] + i.second;que.push({ dis[i.first], i.first });}}}
}
int main() {int n, m, min1, max1;scanf("%d%d%d%d", &n, &m, &min1, &max1);int u, v, w;for (int i = 0; i < m; ++i) {scanf("%d%d%d", &u, &v, &w);add_edge(u, v, w);}memset(dis, INF, sizeof(dis));dis[0] = 0;dij();int ans = 0;// 枚举所有的边 起点能否到达 且大于一点 此边的任何一个点 就说明该条边可以被选用for (int i = 0; i < cnt; ++i) {int u = edge[i].first; int v = edge[i].second; int dist = min(dis[u], dis[v]);if ((dist << 1) < max1) ans++;}printf("%d\n", ans);return 0;
}