洛谷代码雀食用不来（恼
原题链接：576.单源最短路 选点
2024-07-02 10:41:27
发布于：浙江
49阅读
0回复
0点赞
洛谷原题是这个
有点不一样，望大佬修改一下可以AC
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
constexpr int N = 100005;
ll f[N],g[N];
int F[N],G[N],fa[N];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void solve() {
int n,m;
scanf("%d %d",&n,&m);
memset(f,127,sizeof(f));
memset(g,127,sizeof(g));
for(int i = 1;i <= n;++i)
fa[i] = i;
for(int i = 1;i <= m;++i) {
int u,v;
scanf("%d %d",&u,&v);
u = find(u),v = find(v);
if(u == v) continue;
fa[u] = v;
}
int r1 = find(1),rn = find(n);
f[r1] = 0,g[rn] = 0;
int cntF = 0,cntG = 0;
for(int i = 1;i <= n;++i) {
int u = find(i);
if(u == r1) F[++cntF] = i;
else if(u == rn) G[++cntG] = i;
}
for(int i = 1;i <= n;++i) {
int u = find(i);
if(u != r1) {
int pre = std::upper_bound(F + 1,F + cntF + 1,i) - F - 1;
f[u] = std::min(f[u],(ll)(i - F[pre]) * (i - F[pre]));
if(pre < cntF) {
++pre;
f[u] = std::min(f[u],(ll)(i - F[pre]) * (i - F[pre]));
}
}
if(u != rn) {
int nxt = std::upper_bound(G + 1,G + cntG + 1,i) - G;
g[u] = std::min(g[u],(ll)(i - G[nxt]) * (i - G[nxt]));
if(nxt > 1) {
--nxt;
g[u] = std::min(g[u],(ll)(i - G[nxt]) * (i - G[nxt]));
}
}
}
ll ans = (ll)(n - 1ll) * (n - 1ll);
for(int i = 1;i <= n;++i) {
int u = find(i);
ans = std::min(ans,f[u] + g[u]);
}
printf("%lld\n",ans);
}
int main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
有帮助，赞一个