题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2125
仙人掌上求最短路
先搞成树,然后树怎么搞,这题就怎么搞
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
using namespace std;
const int MAXN = 10000+9;
int n,m,Q,lowlink[MAXN],num[MAXN],dis[MAXN],nxt[MAXN*4],to[MAXN*4],head[MAXN],cost[MAXN*4];
int ring_cnt,fa[MAXN][16],dep[MAXN],length[MAXN],ring_num[MAXN],ori[MAXN],que[MAXN],fro;
vector<int> rings[MAXN];
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline void AddEdge(int a, int b, int c){
static int T = 0;
to[++T] = b; nxt[T] = head[a]; head[a] = T; cost[T] = c;
to[++T] = a; nxt[T] = head[b]; head[b] = T; cost[T] = c;
}
void DFS(int w, int f){
static int T = 0; fa[w][0] = f;
lowlink[w] = num[w] = ++T; que[++fro] = w;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
if (!num[to[i]]) {
DFS(to[i], w);
if (lowlink[to[i]] > num[w]) fro--;
else if (lowlink[to[i]] < num[w]) lowlink[w] = lowlink[to[i]];
else {
ring_cnt++; int nw = que[fro--];
while (nw != w) {
rings[ring_cnt].push_back(nw);
nw = que[fro--];
}
rings[ring_cnt].push_back(w); que[++fro] = w;
}
} else lowlink[w] = min(lowlink[w], num[to[i]]);
}
}
inline void prework(){
for (int k=1;k<=ring_cnt;k++) {
int size = rings[k].size();
int rt = rings[k][size-1],tmp=0;
for (int i=1;i<=size;i++) que[i] = rings[k][i-1];
que[0] = rt; que[size+1] = que[1];
for (int i=1;i<size;i++) ring_num[que[i]] = k, fa[que[i]][0] = rt;
for (int i=1;i<=size;i++) {
for (int j=head[que[i]];j;j=nxt[j]) {
if (to[j] == que[i-1]) to[j] = 0, tmp += cost[j];
else if (to[j] == que[i+1]) to[j] = 0;
}
ori[que[i]] = tmp;
} ori[rt] = 0; length[k] = tmp;
for (int i=1;i<size;i++) AddEdge(rt,que[i],min(ori[que[i]], tmp-ori[que[i]]));
}
}
void GetDis(int w){
for (int i=head[w];i;i=nxt[i]) if (!dis[to[i]] && to[i])
dis[to[i]]=dis[w]+cost[i], dep[to[i]] = dep[w] + 1, GetDis(to[i]);
}
inline void LCA_init() {
for (int k=1;k<=15;k++) for (int i=1;i<=n;i++)
fa[i][k] = fa[fa[i][k-1]][k-1];
}
inline int LCA(int a, int b, int &l1, int &l2){
if (dep[a] < dep[b]) swap(a,b);
for (int k=15;~k;k--) if (dep[fa[a][k]] >= dep[b]) a = fa[a][k];
l1 = l2 = a;
if (a == b) return a;
else {
for (int k=15;~k;k--) if (fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k];
l1 = a, l2 = b; return fa[a][0];
}
}
int main(){
n = read(); m = read(); Q = read();
for (int i=1,a,b,c;i<=m;i++)
a = read(), b = read(), c = read(),
AddEdge(a, b, c);
DFS(1,0); prework();
dis[1] = dep[1] = 1; GetDis(1); LCA_init();
for (int i=1,a,b,r,lca1,lca2;i<=Q;i++){
a = read(); b = read();
r = LCA(a, b, lca1, lca2);
if (ring_num[lca1] && ring_num[lca1] == ring_num[lca2]) {
int len = abs(ori[lca1]-ori[lca2]);
len = min(len, length[ring_num[lca1]]-len);
printf("%d\n",dis[a]-dis[lca1]+dis[b]-dis[lca2]+len);
} else printf("%d\n",dis[a]+dis[b]-2*dis[r]);
}
return 0;
}
另外,这份代码在预处理环那里有问题
会被一个点连了几个环的情况卡成翔
正确的写法,参见BZOJ_1023