脚本宝典收集整理的这篇文章主要介绍了CF1483D Useful Edges 题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
Codeforces Luogu
(n) 个点 (m) 条边的图。 (q) 次询问，每次询问将 (x) 到 (y) 的所有距离不超过 (k) 的路径上边染黑 问最后有几条黑边。
有一个 (mathcal O(mq+n^3)) 的暴力，就是先 Floyd 求最短路。 然后再对于每条边，暴力 (O(q)) 计算它到所有询问短点的距离和，可以得知有多少黑边。
优化这个暴力，发现点数是 (O(n)) 的，把询问信息挂在点上就可以 (O(nm))。 设 (f_{i,x}) 表示一个 (irightarrow j) 的询问到 (x) 使得剩下距离最大的最大值。 然后就可以把 (mathcal O(mq)rightarrowmathcal O(mn+qn))。 就做完了。
//Coded by leapfrog on 2021.11.04 {{{
//是啊，你就是那只鬼了，所以被你碰到以后，就轮到我变成鬼了
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=605,M=N*N/2;int n,m,Q,fr[M],tw[M];ll ds[N][N],we[M],qr[N][N];
struct ${int y,w;};vector<$>v[N];
int main()
{
read(n,m),memset(ds,0x3f,sizeof(ds));for(int i=1;i<=n;i++) ds[i][i]=0;
for(int i=1;i<=m;i++) read(fr[i],tw[i],we[i]),ds[fr[i]][tw[i]]=ds[tw[i]][fr[i]]=we[i];
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ds[i][j]=min(ds[i][k]+ds[k][j],ds[i][j]);
int Q;read(Q);for(int i=1,x,y,w;i<=Q;i++) read(x,y,w),v[x].push_back(($){y,w}),v[y].push_back(($){x,w});
memset(qr,~0x3f,sizeof(qr));for(int i=1;i<=n;i++) qr[i][i]=0;
for(int x=1;x<=n;x++) for(int i=1;i<=n;i++)//i->x,y->j,i->x 使得剩下最长
for(auto j:v[i]) qr[i][x]=max(qr[i][x],j.w-ds[x][j.y]);
int cnt=0;for(int i=1,fg=0;i<=m;i++,cnt+=fg,fg=0)
for(int k=1;k<=n&&!fg;k++) fg|=(qr[k][tw[i]]>=we[i]+ds[k][fr[i]]);
return printf("%dn",cnt),0;
}
以上是脚本宝典为你收集整理的CF1483D Useful Edges 题解全部内容，希望文章能够帮你解决CF1483D Useful Edges 题解所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。