[JOI 2024 Final] 建设工程 2
题意
给出一张图和 \(S\)，\(T\)。可在任意两点 \(u,v(u<v)\) 之间添加一条长度为 \(L\) 的边（只可添加一次）。
求有多少种添加方案使得 \(S\) 到 \(T\) 的最短路长度 \(\le K\)。
思路
首先，若 \(S\) 到 \(T\) 的最短路已经 \(\le K\)，答案为 \(\frac{n \times (n - 1)}{2}\)。
然后求出 \(S\) 为源点的最短路和 \(T\) 为源点的最短路。
对于点 \(u,v\)，若 \(dis_{S,u}+L+dis_{v,T} \le K\)，则在 \(u,v\) 之间连一条边是可行的。
移项可得 \(dis_{v,T}\le K - L - dis_{S,u}\)，枚举 \(dis_{S,u}\)，则右侧是定值。
可将 \(dis_v\) 排序， 在 \(dis_{v}\) 中二分最后一个小于等于 \(K-L-dis_{S,u}\) 的数，统计答案即可。
这样可能会发现问题，如果我二分出来包含 \(u = v\) 的情况怎么办？
若 \(dis_{S,u} + L + dis_{v,T} \le K\)，则 \(dis_{S,T}\) 已经 \(\le K\)，会被最开始的特判判掉。
这样可能还有问题，如果我二分出来 \((u,v)\) 和 \((v,u)\) 都统计了一遍怎么办？
若 $dis_{S,u}+L+dis_{v,T}\le K $ 且 \(dis_{S,v}+L+dis_{u,T} \le K\)，则两式相加得 \(2dis_{S,T}+2L\le K\) 可推出 \(dis_{S,T}\le K\)，这也会被特判掉。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int tot, ver[N << 1], nxt[N << 1], edge[N << 1], head[N];
int n, m, s, t, l, k, dis[2][N], ans;
bool vis[N];
void add(int x, int y, int z) {
ver[++ tot] = y;
nxt[tot] = head[x];
head[x] = tot;
edge[tot] = z;
}
struct node {
int id, dis;
};
bool operator < (node x, node y) {
return x.dis > y.dis;
}
priority_queue <node> Q;
void dijkstra(int S, int id) {
memset(vis, 0, sizeof(vis));
memset(dis[id], 0x3f, sizeof(dis[id]));
dis[id][S] = 0;
Q.push({S, 0});
while (!Q.empty()) {
int x = Q.top().id; Q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i], z = edge[i];
if (dis[id][y] > dis[id][x] + z) {
dis[id][y] = dis[id][x] + z;
Q.push({y, dis[id][y]});
}
}
}
}
signed main() {
cin >> n >> m >> s >> t >> l >> k;
for (int i = 1; i <= m; i ++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dijkstra(s, 0);
dijkstra(t, 1);
if (dis[0][t] <= k) {
cout << n * (n - 1) / 2 << '\n';
return 0;
}
sort(dis[1] + 1, dis[1] + n + 1);
for (int i = 1; i <= n; i ++) {
int x = k - l - dis[0][i];
int pos = upper_bound(dis[1] + 1, dis[1] + n + 1, x) - dis[1] - 1;
ans += pos;
}
cout << ans << "\n";
return 0;
}