问题的难点在于首先要发现这不是多组询问。首先显然可以使用 Floyd 算法求出全源最短路。最暴力的算法枚举边再枚举每个三元组时间复杂度为 (4)O(n4)。然后考虑优化假设我们之前枚举出来的边两端为 x 和 y 边长为 w并且设其路径为从 u 到 x 再从 y 到 v。那么距离就可以表示为,,≤disu,x​wdisy,v​≤l考虑如何优化我们要统计有用边的个数因此我们肯定要枚举边也就是说 u 和 v 只能枚举其中一个才能使时间复杂度为 (3)O(n3)。所以考虑把式子转换一下,≤−,disu,x​w≤l−disy,v​那么我们已枚举出了边再枚举出 u 就可以得到右边式子结果最大的情况了。此时记录 ,fi,j​ 表示 v 和 l 是 ui 的一个三元组j 是 y 时的最大右边式子的值。即可轻松得到答案cpp#includebits/stdc.h #define int long long using namespace std; int n,m,dis[605][605],f[605][605],q; struct P{ int u,v,w; }e[400005]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinnm; memset(dis,0x3f,sizeof(dis)); for(int i1;im;i){ cine[i].ue[i].ve[i].w; dis[e[i].u][e[i].v]dis[e[i].v][e[i].u]e[i].w; } for(int i1;in;i)dis[i][i]0; for(int k1;kn;k){ for(int i1;in;i){ for(int j1;jn;j)dis[i][j]min(dis[i][k]dis[k][j],dis[i][j]); } } cinq; for(int i1,u,v,l;iq;i){ cinuvl; for(int y1;yn;y)f[u][y]max(f[u][y],l-dis[y][v]),f[v][y]max(f[v][y],l-dis[y][u]); } int ans0; for(int i1;im;i){ int xe[i].u,ye[i].v,we[i].w; for(int u1;un;u){ if(dis[u][x]wf[u][y]){ ans; break;