CF1051F
给定一个张点数 \(n\) 边数 \(m\) 的图,\(m-n\le 20\),\(T\) 组询问求两点间最短路。
那么搞出随便一个生成树,每次用 \(O(m-n)\) 条非树边两个端点更新答案。具体是 dij 预处理这些点到其他点的距离。
犯了一个小错误,就是说用非树边更新了。但是实际上不一定会走该非树边。
还有就是 unique vector 以后需要删掉返回迭代器及以后的东西。不太能直接遍历。。
还有就是求 dfs 树的一些小问题,还有就是 dij 中使用引用的话,不能用 memset,注意 Wall 和 Wextra 的提示!
经过肢解的代码
void dfs1(int x,int fat) {
vis[x] = ++vis[0];
...
for(auto h:G[x]) {
int y=h.fi,w=h.se;
if(y==fat) continue;
if(vis[y]) {
if(vis[y] > vis[x]) {
S.ep(x), S.ep(y);
}
continue;
}
dis[y] = dis[x] + w;
dfs1(y,x);
}
}
ll d[43][MAX];
int id[MAX];
priority_queue<pair<ll, int>,vector<pair<ll, int>>, greater<pair<ll, int>>> q;
void dij(int x, ll *c) {
for(int i=1;i<=n;++i) {
c[i] = 0x3f3f3f3f3f3f3f3f;
vis[i] = 0;
}
// memset(vis,0,sizeof(vis));
// memset(c,0x3f,sizeof(c));
}
signed main() {
input();
sort(S.begin(), S.end());
auto p = unique(S.begin(), S.end());
S.erase(p, S.end());
for(int x : S) {
// printf("%d ",x);
// if(id[x]) continue;
id[x] = ++id[0];
dij(x, d[id[x]]);
}
int T=read();
while(T--) {
int u,v;
u=read(),v=read();
ll ans = dis[u] + dis[v] - 2ll * dis[LCA(u,v)];
// for(auto e:edge){
// int w=e.fi, x=e.se.fi, y=e.se.se;
// ans = min(ans, d[id[x]][u] + w + d[id[y]][v]);
// }
for(int x : S) {
ans = min(ans, d[id[x]][u] + d[id[x]][v]);
}
printf("%lld\n", ans);
}
return 0;
}
标签:,dij,int,ll,vis,ep,dis
From: https://www.cnblogs.com/Lates/p/16857620.html